2024杭电多校第5场

（似乎第四场还没补）（没事，问题不大）

5

1002 Array-Gift （hdu7482）

某种意义上的找规律题？

若序列中存在 \(a_i = gcd(a_1,a_2,...a_n)\)，则显然 \(a_i\) 为序列中的最小值，可通过 \(n-1\) 次取模操作，将其他数变成 \(0\)，由于原序列中 \(a>0\)，不存在更少的操作次数。若不存在上述 \(a_i\)，可通过 \((a_i + x)\space mod\space a_j\) 两步操作凑出其他数的 \(gcd\)，故最多操作次数为 \(n + 1\). 接下来讨论操作 \(n\) 次的情况，这其中必有 \(n-1\) 次取模操作，因此只需考虑另外一次操作的类别。对原序列升序排序，设其 \(gcd\) 为 \(g\).

1）若进行 \(a_i\space mod\space a_j = b\)，使当前的 \(gcd = g'\) 存在于序列中，则 \(b=g'\) 或 \(g'|b\). \(b=g'\) 时有 \(b|a_j\)，故 \(b|a_i\) 成立，\(b|g\) 即满足要求。由于对其他数提前取余不会改变 \(g'\)，此情况下不用考虑操作次序；\(g'|b\) 时由升序排列 \(g' = a_1\)，若 \(a_1|b\)，则有 \(a_1 | a_i\)，即对原序列已有 \(a_1 = g\)，不符合条件。

2）若进行 \(a_i + x = c\)，则 \(c=g'\) 或 \(g'|c\). \(c=g'\) 时必有 \(i=1\)，\(a_1 \leq gcd(a_2,a_3,...a_n)\) 时可凑出满足条件的 \(c\)；\(g'|c\) 时 \(g' = a_1\)，注意到 \(gcd(g',a_j)\leq g'\)，对更少的数求 \(gcd\) 显然更优，因此可预先将所有 \(a_i\space mod\space a_j = 0\) 操作完毕。