【 8.7 】 source code - card to LCM with GCD 】 【 】

#968. 抽卡

题意：

题解：UNICORN Programming Contest 2021(AtCoder Beginner Contest 225) 部分题目题解

思路：考虑 DP .先排一下序,然后定义 $dp(i,j)$ 表示后 $i$ string selection $j$ The smallest lexicographic order of spellings.$dp(i,j)=\min (dp(i+1,j),s_i+dp(i+1,j-1))$ ,注意边界条件.

There are two things to say：

1. 我们要按照 $a+b<b+a$ 的方式排序,而不是 $a<b$ 的方式.For example, in order of the latter $b,ba$ ,But the spelling is not the least lexicographical order.We sort by the former,就能保证 A subset of strings in minimal lexicographic concatenation 等于 These strings are spelled from left to right according to the sorted subscripts.
2. As for why it fell DP ,Probably because of the front $i-1$ Minimum lexicographical order of strings,Concatenate with the current string,not necessarily ex $i$ Minimum lexicographical order of strings.不是很懂.

AC代码：http://oj.daimayuan.top/submission/325124

#953. LCM与GCD

题意：

思路：Another formula question.等价于 $x\cdot \frac{a}{\gcd (a,b)}\cdot \frac{b}{\gcd (a,b)}-y=\frac{k}{\gcd (a,b)}$ ,容易知道 $\gcd (a,b)$ 一定是 $k$ 的因子,The root sign enumerates the factors.

for an enumerated factor,Let's push the formula again： $\frac{a}{\gcd (a,b)}\cdot \frac{b}{\gcd (a,b)}=\frac{\frac{k}{\gcd (a,b)}+y}{x}=M$ ,The question turns into how many logarithms are coprime and the product is $M$ .The root sign enumerates the types of prime factors.

AC代码：http://oj.daimayuan.top/submission/325163