Pollard Rho （大数分解算法）

RhoPollard Rho是一个著名的大数质因数分解算法，它的实现基于一个神奇的算法：MillerRabinMillerRabin素数测试。

Pollard_rho算法的大致流程是先判断当前数是否是素数（Miller_rabin）了，如果是则直接返回。如果不是素数的话，试图找到当前数的一个因子（可以不是质因子）。然后递归对该因子和约去这个因子的另一个因子进行分解。

https://lunatic.blog.csdn.net/article/details/104218095

https://blog.csdn.net/maxichu/article/details/45459533

#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
typedef long long ll ;
#define int ll
#define mod 1000000007
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j)  for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//ll lcm(ll a , ll b){return a*b/gcd(a,b);}
ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define SC scanf
#define INF  0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
using namespace std;
const int N = 1e6+100;
const int maxn = 2e5+9;
int pr;

int quickmul(int a , int b , int m){
    return  ((a * b - (ll)(long double)(a/m*b) * m)+m)%m ;
}

int quickpow(int a , int b , int m){
    int ans = 1 ;
    while(b){
        if(b&1) ans = quickmul(ans , a , m) ;
        b >>= 1 ;
        a = quickmul(a , a , m);
    }
    return ans ;
}
inline ll gcd(ll a, ll b)
{ //听说二进制算法特快
    if (!a)
        return b;
    if (!b)
        return a;
    int t = __builtin_ctzll(a | b);
    a >>= __builtin_ctzll(a);
    do
    {
        b >>= __builtin_ctzll(b);
        if (a > b)
        {
            ll t = b;
            b = a, a = t;
        }
        b -= a;
    } while (b);
    return a << t;
}

bool Miller_Rabin(int n){
    if(n == 46856248255981ll || n < 2) return false;
    if(n == 2 || n == 3 || n == 7 || n == 61 || n == 24251) return true;
    if(!(n&1) || !(n%3) || !(n%61) || !(n%24251)) return false;
    int m = n - 1 , k = 0 ;
    while(!(m&1)) k++ , m>>=1 ;// 分解2^s * t = n - 1
    rep(i , 1 , 20){
        int a = rand() % (n - 1) + 1 , x =  quickpow(a , m , n) , y;
        rep(j , 1 , k){
            y = quickmul(x , x , n);
            if(y == 1 && x != 1 && x != n - 1) return false;//二次测探
            x = y ;
        }
        if(y != 1) return false;//费马小定理
    }
    return true;
}
ll Pollard_Rho(ll x)
{
    ll n = 0, m = 0, t = 1, q = 1, c = rand() % (x - 1) + 1;
    for (ll k = 2;; k <<= 1, m = n, q = 1)
    {
        for (ll i = 1; i <= k; ++i)
        {
            n = (quickmul(n, n, x) + c) % x;
            q = quickmul(q, abs(m - n), x);
        }
        t = gcd(x, q);
        if (t > 1)
            return t;
    }
}
map<long long, int> m;
void fid(ll n)
{
    if (n == 1)
        return;
    if (Miller_Rabin(n))
    {
        pr = max(pr, n);
        m[n]++;
        return;
    }
    ll p = n;
    while (p >= n)
        p = Pollard_Rho(p);
    fid(p);
    fid(n / p);
}


void solve(){
    int n ;
    m.clear();
    scanf("%lld", &n);
    pr = 0;
    fid(n);
    if (pr == n)
        puts("Prime");
    else{
        printf("%lld\n", pr);
        for (map<long long, int>::iterator c = m.begin(); c != m.end();){
            printf("%lld^%d", c->first, c->second);
            if ((++c) != m.end())
                printf(" * ");
        }
        printf("\n");
    }
}

signed main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(0); cout.tie(0);
    int t ;
    cin >> t ;
    while(t--){
        solve();
    }
}

Pollard Rho （大数分解算法）

推荐阅读