526互联

Pollard_Rho（大数分解质因子）

发布时间 2023-07-10 16:46:07作者: 陌上&初安

例题：P4718

题意：

T组数据，输入T个数，对于每个数 n 判断是不是素数，如果是素数输出："Prim",否则输出他的最大质因子。（1 < T < 350, 1 <= n <= 1e18）。

思路：

很典型的一道模板题，Pollard_Rho算法能够在$ O(n ^ {1/4})$的时间内找到 n 的一个质因子 p ,然后再递归计算 \(n' = n / p\), 直到 n 为素数为止，通过这样的方法将 n 进行质数分解。

模板代码：

// -----------------
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
#define endl '\n'
typedef long long ll;

using namespace std;

const int N = 1e5 + 10;
ll x, y, a[N], max_factor;
ll n;

struct BigIntegerFactor
{
    const static int N = 1e6 + 7;
    ll prime[N], p[N], fac[N], sz, cnt = 0;
    
    inline ll mul(ll a, ll b, ll mod)
    {
        if(mod <= 1e9) return a * b % mod;
        return (a * b - (ll)((long double)a / mod * b + 1e-8) * mod + mod ) % mod;
    }
    
    void init(int maxn)
    {
        int tot = 0;
        sz = maxn - 1;
        for(int i = 1; i <= sz; i ++) p[i] = i;
        for(int i = 2; i <= sz; i ++)
        {
            if(p[i] == i) prime[tot ++] = i;
            for(int j = 0; j < tot && 1ll * i * prime[j] <= sz; j ++)
            {
                p[i * prime[j]] = prime[j];
                if(i % prime[j] == 0) break;
            }
        }
    }
    
    ll qpow(ll a, ll x, ll mod)
    {
        ll res = 1ll;
        while(x) 
        {
            if(x & 1) res = mul(res, a, mod);
            a = mul(a, a, mod);
            x >>= 1;
        }
        return res;
    }
    
    bool check(ll a, ll n)  // 二次探测原理检验n
    {
        ll t = 0, u = n - 1;
        while(!(u & 1)) t ++, u >>= 1;
        ll x = qpow(a, u, n), xx = 0;
        while(t --)
        {
            xx = mul(x, x, n);
            if(xx == 1 && x != 1 && x != n - 1) return false;
            x = xx;
        }
        return xx == 1;
    }
    
    bool miller(ll n, int k)  
    {
        if(n == 2) return true;
        if(n < 2 || !(n & 1)) return false;
        if(n <= sz) return p[n] == n;
        for(int i = 0; i <= k; i ++)  // 测试k次
        {
            if( !check(rand() % (n - 1) + 1, n) ) return false;
        }
        return true;
    }
    
    inline ll gcd(ll a, ll b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    inline ll Abs(ll x)
    {
        return x < 0 ? -x : x;
    }
    
    ll Pollard_rho(ll n)  // 基于路径倍增的Pollard_Rho算法
    {
        ll s = 0, t = 0, c = rand() % (n - 1) + 1, v = 1, ed = 1;
        while(1)
        {
            for(int i = 1; i <= ed; i ++)
            {
                t = (mul(t, t, n) + c) % n;
                v = mul(v, Abs(t - s), n);
                if(i % 127 == 0)
                {
                    ll d = gcd(v, n);
                    if(d > 1) return d;
                }
            }
            ll d = gcd(v, n);
            if(d > 1) return d;
            s = t;
            v = 1;
            ed <<= 1; 
        }
    }
    
    void getfactor(ll n)
    {
        if(n <= sz)
        {
            while(n != 1) fac[cnt ++] = p[n], n /= p[n];
            max_factor = max_factor > p[n] ? max_factor : p[n];
            return;
        }
        if(miller(n, 6))
        {
            fac[cnt ++] = n;
            max_factor = max_factor > n ? max_factor : n;
        }
        else
        {
            ll d = n;
            while(d >= n) d = Pollard_rho(n);
            getfactor(d);
            getfactor(n / d);
        }
        return;
    }
} Q;

void solve()
{
	max_factor = -1;
	cin >> n;
	Q.getfactor(n);
	if(max_factor == n) cout << "Prime" << endl;
	else cout << max_factor << endl;
}

signed main()
{
    IOS
    //Q.init(N-1);  // 仅需要分解大数的质因数且代码超时
    int T = 1;
    cin >> T;
    while(T --) {solve(); }
    return 0;
}