CF1305F Kuroni and the Punishment

给定 $n$ 个数 $a_i$,每次可以将其中一个 $\texttt{+1}$ 或者 $\texttt{-1}$。求最少多少次操作可以让整个序列的 $\gcd > 1$。
$n\le 10^5,a_i\le 10^{12}$。

$\texttt{Solution}$

神题呐!

首先,操作次数上限肯定是 $n$,因为可以把所有值变成偶数,当任意 $a_i$ 都是奇数的时候就需要操作 $n$ 次。

那么,如果操作次数 $\ge 2$ 的数字个数,一定不超过 $\lfloor \dfrac{n}{2} \rfloor$ 个。因为如果超过 $\lfloor \dfrac{n}{2} \rfloor$ 个,总次数就超过了 $n$ 的上限。

考虑随机化算法。

取出其中 $k$ 个数字,放入集合 $S$,我们认为他们中至少有一个操作了 不超过一次。那对于任意 $a_i\in S$,都将 $a_i,a_i+1,a_i-1$ 质因数分解,将所有质因数存下来。这里显然质数只要筛到 $\sqrt{10^{12}}=10^6$ 即可。

现在得到了若干质数,他们都有可能是最后的 $\gcd$ 的因数。因此,对每一个质数都 $\mathcal{O}(n)$ 计算一遍。大概就是找到质数 $p$ 的某一些倍数,使得他们和每个 $a_i$ 分别最接近,作差即可。

现在对于一个数字 $a_i$,他若被选出,他的操作次数 $\ge 2$ 的概率不超过 $\dfrac{1}{2}$。

所以随机选 $k$ 个,整个集合 $S$ 中任意数字操作次数 $\ge 2$ 的概率是 $\dfrac{1}{2^k}$,在 $k \ge 30$ 的时候就几乎不可能了。

也就是在 $k \ge 30$ 时,这个 $\gcd$ 就几乎一定可以被考虑到了,这里 $k$ 我取的是 $100$。

记得 $\texttt{srand}$......推荐种子5224999