poj1741，poj1811(pollard_rho模板)

題目鏈接: http://poj.org/problem?id=1811

?

題意: 判斷一個數 n (2 <= n < 2^54)是否為質數, 是的話輸出 "Prime", 否則輸出其第一個質因子.

?

思路: 大數質因子分解, 直接用 pollard_rho (詳情參見: http://blog.csdn.net/maxichu/article/details/45459533) 模板即可.

poj1741？?

代碼:

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

const int MAXN = 1e2;
const int repeat = 8;//repeat為檢測次數,判斷錯誤率為4^-repeat,一般8~10就夠了

ll get_mult(ll a, ll b, ll c){//返回a*b%c
    a %= c;
    b %= c;
    ll ret = 0;
    while(b){
        if(b & 1){
            ret += a;
            if(ret >= c) ret -= c;
        }
        b >>= 1;
        a <<= 1;
        if(a >= c) a -= c;
    }
    return ret;
}

ll get_pow(ll x, ll n, ll mod){//返回x^n%mod
    ll ret = 1;
    x %= mod;
    while(n){
        if(n & 1) ret = get_mult(ret, x, mod);
        x = get_mult(x, x, mod);
        n >>= 1;
    }
    return ret;
}

//通過 a^(n-1) = 1(mod n) 來判斷n是否為素數
//n-1 = x*2^t 中間使用二次探測定理
//是合數返回true,不一定是合數返回false
bool cherk(ll a, ll n, ll x, ll t){
    ll ret = get_pow(a, x, n);
    ll last = ret;
    for(int i = 1; i <= t; i++){
        ret = get_mult(ret, ret, n);
        if(ret == 1 && last != 1 && last != n - 1) return true;
        last = ret;
    }
    if(ret != 1) return true;
    return false;
}

bool Miller_Rabin(ll n){
    if(n < 2) return false;
    if(n == 2) return true;
    if(!(n & 1)) return false;//偶數
    ll x = n - 1, t = 0;
    while(!(x & 1)){
        x >>= 1;
        t++;
    }
    // srand(time(NULL));
    for(int i = 0; i < repeat; i++){
        ll a = rand() % (n - 1) + 1;
        if(cherk(a, n, x, t)) return false;
    }
    return true;
}

ll factor[MAXN];
int tot;//n的質因子個數

ll get_gcd(ll a, ll b){
    ll tmp;
    while(b){
        tmp = a;
        a = b;
        b = tmp % b;
    }
    return a >= 0 ? a : -a;
}

ll pollard_rho(ll x, ll c){//返回x的一個因子
    ll i = 1, k = 2;
    // srand(time(NULL));
    ll x0 = rand() % (x - 1) + 1;
    ll y = x0;
    while(1){
        i++;
        x0 = (get_mult(x0, x0, x) + c) % x;
        ll d = get_gcd(y - x0, x);
        if(d != 1 && d != x) return d;
        if(y == x0) return x;
        if(i == k){
            y = x0;
            k += k;
        }
    }
}

void findfac(ll n, int k){//對n質因分解并將結果保存到factor中
    if(n == 1) return;
    if(Miller_Rabin(n)){
        factor[tot++] = n;
        return;
    }
    ll p = n;
    int c = k;//c防止死循環
    while(p >= n){
        p = pollard_rho(p, c--);
    }
    findfac(p, k);
    findfac(n / p, k);
}

int main(void){
    ll n;
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        if(Miller_Rabin(n)) cout << "Prime" << endl;
        else{
            tot = 0;
            findfac(n, 107);
            ll sol = factor[0];
            for(int i = 1; i < tot; i++){
                sol = min(sol, factor[i]);
            }
            cout << sol << endl;
        }
    }
    return 0;
}

?