miller-rabin
这个东西是用来判质数的。
一般的质数判断是$O(\sqrt{n})$的，当$n$很大的时候复杂度无法接受。我们换个思路：质数满足一些性质。如果我们现在问的这个数满足这些性质，那么这个数就可能是个质数，否则就一定不是。
费马小定理
对于质数$p$，有
如果对于一对$a p$使得上式成立，那么$p$就可能是个质数。之所以说可能，是因为存在一些合数$n$，存在$a$满足$a^{n - 1} \equiv 1 \pmod n$，比如$2^{340} \equiv 1 \pmod {341}$而$341 = 11 \times 13$。这类数称作伪素数。例子中的$341$虽然在$a=2$的时候无法判断它是质数还是合数，但$a=3$的时候就可以知道了。这就启发我们多次随机$a$来检验。
我们现在这个方法看起来很棒，但在某些情况下错误率会大大提升，因为有一些合数$n$，对于所有$a \perp n$都能使费马小定理成立，比如$561$。这种数叫卡迈克尔数。虽然当$a n$不互质时$n$就暴露了，但出错的概率还是很大。我们需要再找个质数的性质来辅助判断。
二次探测定理
对于奇质数$p$和正整数$e$，有
只有两个解$x = \pm 1$。
如果我们找到一个数$a \neq \pm 1$使得$a ^ 2 \equiv 1 \pmod n$，这就能说明$n$不是个质数。把这个东西和费马小定理结合起来，就是miller-rabin了。
miller-rabin素性检验
卡迈克尔数有个性质，就是一定是3个以上互不相同的质数的乘积，所以卡迈克尔数一定可以通过二次探测定理检验出来。所以如果一个数两个东西都不能排除它是质数的可能性，那么它就是质数。
先上费马小定理：对于质数$n$，有
然后再上二次探测定理，得
对于一个$a$，如果上式右边$=1$，那我们可以继续开方，直到指数为奇数或右边$= -1$。
反过来，对于要检验的$n$，我们把$n - 1$分解成$d \times 2^t$（$d$为奇数），如果存在一个$a$使得对任意$r \in [0, t)$满足
那么$n$就一定不是质数。但我们不能把所有$a$都试一遍，所以我们可以随机几个$a$，如果都没问题的话，那就当它是吧。
pollard’s rho
这个东西是用来分解大数的，它可以求出大数的一个因子（不一定是质因子）。通常结合miller-rabin先判断这个是不是质数，再进行分解，当然如果题目告诉你它是合数，那就不需要了。
生日悖论
这个应该很有名吧。原始版本就是一个$n$个人的班上有多大的概率至少有两个人生日相同。这个概率就是
在$n = 23$的时候概率已经过半了，而$n = 60$的时候这个值已经超过$0.99$了。这是个非常好的性质。推广一下，两个人的差是某个定值的概率也是这样的。原始版本就是差$=0$时的情况。
pollard’s rho
回到这个上面来，我们用随机函数$f(x) = x^2 + c \mod n$和$x_0$构造一个随机序列$x_i = f(x_{i - 1})$。根据生日悖论，$\{x_k\}$很快就会循环。再来个序列$\{x_k \mod p\}$，其中$p$是$n$的一个因数（这是我们要求的）。当$\{x_k \mod p\}$成环时，即$\{x_i \mod p = x_j \mod p\}$时，那么$p | x_i - x_j$，这时如果$x_i \neq x_j$，那么显然$p = (|x_i - x_j|, n)$。当然如果$\{x_k\}$已经循环了$\{x_k \mod p\}$还没有循环，那就换个$x_0$和$c$再试试吧。还有一个问题：怎么判环呢？把$\{x^k\}$全部存下来显然不现实。Floyd发明了一个神奇的东西，就是维护两个位置$a$和$b$，开始时两者在同一位置，然后每一轮$a$走一步，$b$走两步。当$b$再次和$a$在同一位置时，就说明找到了环。根据生日悖论，环的大小是$\sqrt{p}$的，而这个找环的算法显然也是$O($环的大小$)$的，所以期望复杂度就是$O(n^{\frac 1 4})$的。
代码
long long mul(long long x, long long y, long long mod)
{
long long ans = 0;
while (y)
{
if (y & 1) ans = (ans + x) % mod;
x = (x + x) % mod;
y >>= 1;
}
return ans;
}
long long Pow(long long x, long long y, long long mod)
{
long long ans = 1;
while (y)
{
if (y & 1) ans = ans * x % mod;
x = x * x % mod;
y >>= 1;
}
return ans;
}
inline long long rd()
{
#ifdef __WIN32
return 1LL * rand() * rand() * rand() * rand();
#else
return 1LL * rand() * rand();
#endif
}
bool miller_rabin(long long x)
{
if (x == 2) return true;
if (x < 2 || x & 1 ^ 1) return false;
int cnt = 0;
long long d = x - 1;
while (d & 1 ^ 1) cnt++, d >>= 1;
for (int i = 0; i < 5; i++)
{
long long a = Powm(rd() % (x - 2) + 2, d, x);
// printf("%lld\n", a);
if (a == 1 || a == x - 1) continue;
bool tf = false;
for (int j = 0; j < cnt; j++)
{
a = mul(a, a, x);
if (a == x - 1) { tf = true; break; }
}
if (!tf) return false;
}
return true;
}
long long gcd(long long x, long long y) { return y == 0 ? x : gcd(y, x % y); }
long long rho(long long x)
{
if (x % 2 == 0) return 2;
long long a = rd() % (x - 1) + 1, b = a, c = rd() % (x - 1) + 1;
while (1)
{
a = (mul(a, a, x) + c) % x;
b = (mul(b, b, x) + c) % x;
b = (mul(b, b, x) + c) % x;
if (a == b) break;
long long hh = gcd(abs(a - b), x);
if (hh > 1) return hh;
}
return -1;
}
void divi(long long n)
{
if (n == 1) return;
if (miller_rabin(n))
{
b.push_back(n);
return;
}
// printf("%lld\n", n);
long long p = rho(n);
while (p == -1) p = rho(n);
divi(p);
divi(n / p);
}