Pollard’s Rho 较大整数因数分解

建议看一下网上找到的文章

如何分解

要分解 $n$ ,只需要找到一个 $d$ 使 $gcd(n,d)\neq 1$ ,然后分别分解 $d$ 和 $\frac{n}{d}$ 即可
但是这个 $d$ 十分难找,根据生日悖论(具体看pdf里的东西),我们随机找两个数 $x_i,x_j$
判断 $gcd(|x_i-x_j|,n)$ 是否为 $1$ ,然后进行继续选取或直接分解,碰中的几率会大很多
于是设 $f_i=f_{i-1}^2+c$ ,然后分别生成(伪)随机数来进行判定
但是程序中需要判断某个大整数是否为素数,这就需要用到 Miller-Rabin算法
发现这样生成 $f$ 可能会生成环,这会导致程序陷入死循环,此时需要跳出
应该如何判断环
有两种判环方法,一种是 $floyd$ 判环,在 pdf 中写了
另一种是 $brent$ 判环
设 $x=f_{2^i+j},y=f_{2^i}$ ,然后判断 $x$ 和 $y$ 是否相等,相等时说明我们已经走了一个环
然后当一轮循环完后,将 $y$ 设为 $f_{2^{i+1}}$ ,将 $x$ 设为 $f_{2^{i+1}+1}$ 继续新一轮循环
不想讲多了,感觉就是玄学

例题

程序

贴个板子,这东西搞得我有点心累
if (!(i & M)) 那个判断我真不知道为什么效果那么大,不加就 TLE,求指点一下

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

#define reg register
#define M 127
typedef long long ll;

ll N;
ll primes[7] = {3, 5, 7, 11, 13, 61, 24251};
ll mx;

inline ll mul (ll x, ll y, ll mod) {
    ll tmp = x * y - (ll)((long double)x / mod * y) * mod;
    return tmp < 0 ? tmp + mod : tmp;
}

inline ll add (ll x, ll y, ll mod) {return (x + y) % mod;}

inline ll quick_pow (ll x, ll p, ll mod) {
    ll ans = 1;
    while (p) {
        if (p & 1) ans = mul(ans, x, mod);
        x = mul(x, x, mod);
        p >>= 1;
    }
    return ans;
}

inline bool isPrime (ll P) {
    if (P < 2) return false;
    if (P == 2) return true;
    if (!(P & 1)) return false;
    ll n = P - 1, t = 0;
    while (!(n & 1)) n >>= 1, t++;
    for (int i = 0; i < 7; ++i) {
        if (primes[i] > P) break;
        if (P == primes[i]) return true;
        ll x = quick_pow(primes[i], n, P), y = x;
        for (int i = 0; i < t; ++i) {
            x = mul(x, x, P);
            if (x == 1 && !(y == 1 || y == P - 1)) return false;
            y = x;
        }
        if (x != 1) return false;
    }
    return true;
}

inline ll gcd (ll a, ll b) {
    while (b ^= a ^= b ^= a %= b);
    return a;
}

inline ll pollardrho (ll n, ll c) {
    if (!(n % 2)) return 2;
    if (!(n % 3)) return 3;
    if (!(n % 5)) return 5;
    if (!(n % 7)) return 7;
    ll x = rand() % (n - 1) + 1, y = x, d = 1, q;
    for (int k = 2; ; k <<= 1, y = x, q = 1) {
        for (int i = 1; i <= k; ++i) {
            x = add(mul(x, x, n), c, n);
            q = mul(q, std::abs(y - x), n);
            if (!(i & M)) {
                d = gcd(q, n);
                if (d > 1) break;
            }
        }
        if (d > 1 || (d = gcd(q, n)) > 1) break;
    }
    return d;
}

void solve (ll n, ll cnt) {
    if (n == 1 || n <= mx) return;
    if (isPrime(n)) {
        mx = std::max(mx, n);
        return;
    }
    ll p = n;
    while (p == n) p = pollardrho(n, cnt--);
    while (!(n % p)) n /= p;
    solve(p, cnt), solve(n, cnt);
}

void print (ll x) {
    if (x > 9LL) print(x / 10LL);
    putchar(x % 10LL + '0');
}

int main () {
    srand(0x66ccf);
    int T;
    read(T);
    while (T--) {
        read(N);
        mx = 0;
        solve(N, 13579246);
        if (N == mx) puts("Prime");
        else print(mx), puts("");
    }
    return 0;
}

sys_con

OIer,常规 / 竞赛都渣得不行