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

标签: 质因数分解, 随机化

添加新评论