素性测试和质因数分解

Miller-Rabin 素性测试

对于一个质数 \(p\)，若正整数 \(x\in [1,p-1]\) 满足 \(x^2\equiv 1\pmod p\)，那么 \(x\equiv 1\pmod p\) 或 \(x\equiv -1\pmod p\)。事实上，在 \(p\) 不是质数的时候，\(x\) 的解可能多于两个，例如 \(3^2\equiv 1\pmod 8\)。

\(p\) 是质数的一个必要条件是 \(\forall a\in [1,p-1],~a^{p-1}\equiv 1\pmod p\)。然而这个条件并非充分，如 \(p=561\)（已经是最小的了）。

而通过上面的结论，我们先分解 \(p-1=r\times 2^t\)（\(r\) 是奇数），考虑 \(a^r\)，不断将这个数字平方，由于最后一定会变为 \(1\)，因此要么一开始就是 \(1\)，要么中间出现一个 \(-1\) 然后变成 \(1\)。Miller-Rabin 指出，只需取 \(a=2,3,5,7,11,13,17,27\) 就可以覆盖 long long 范围内的所有合数。因此时间复杂度约为 \(8\times \log n\)。

Pollard-Rho 质因数分解

Pollard-Rho 可以在期望 \(O(n^{1/4})\) 内找到 \(n\) 的一个非平凡因子，因此可以用于大数的质因数分解。

考虑函数 \(f(x)=x^2+C\)，那么有 \(f(x+n)\equiv f(x)\pmod n\)。考虑数列 \(a,f(a),f(f(a)),\cdots\pmod n\)，它期望在 \(\sqrt n\) 的时间内进入循环。而对于 \(n\) 的一个非平凡因子 \(d\)，上面的数列在模 \(d\) 意义下期望在 \(\sqrt d\) 的时间内进入循环。只要数列在进入 \(n\) 的循环前进入 \(d\) 的循环，考虑环上一个数字和绕一圈之后的数字，记其差值为 \(t\)，那么 \(t\ne n\) 且 \(d|t\)，取 \(d=\gcd(t,n)\) 即可。

由于 \(n\) 不是质数时，至少存在一个 \(\le \sqrt n\) 的非平凡因子，因此进入环的步数期望为 \(n^{1/4}\)。设两个指针 \(p_1,p_2\)，一个一次走一步，一个一次走两步，作差并累乘，隔 \(\log\) 步跑一次辗转相除，时间复杂度 \(O(n^{1/4})\)。

P5071 [Ynoi Easy Round 2015] 此时此刻的光辉

按三次根号分治，小于 \(1000\) 的质数只有 \(168\) 个，直接暴力前缀和；剩下的数最多有两个质因子，直接 PR 分解出来跑莫队即可。