POJ 1811 Prime Test（pollard_rho 算法，裸题）

pollard_rho 算法的裸题
题目意思：
给出一个数n，如果n是素数，输出 Prime， 否则输出n的最小素因子

本题要点：
1、pollard_rho 算法求出 n的所有素因子。输出最小的即可。

#include <cstdio>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
const int repeat = 20, MaxN = 110;
ll ct, n, min_prime;
int T;ll gcd(ll a, ll b)
{
    return b? gcd(b, a % b) : a;
}ll multi(ll a, ll b, ll m)	//求 a*b % m
{
    ll ans = 0;a %= m;while(b){
    if(b & 1)ans = (ans + a) % m;b /= 2;a = (a + a) % m;}return ans;
}ll pow(ll a, ll b, ll m)	//求 a^b % m
{
    ll ans = 1;a %= m;while(b){
    if(b & 1)ans = multi(a, ans, m);b /= 2;a = multi(a, a, m);}ans %= m;return ans;
}bool Miller_Rabin(ll n)
{
    if(2 == n || 3 == n)return true;if(n % 2 == 0 || 1 == n)	//偶数和1return false;ll d = n - 1;	// n - 1 分解为 2^s * dint s = 0;while(!(d & 1)){
    ++s, d >>= 1;}srand((unsigned)time(NULL));for(int i = 0; i < repeat; ++i)	//重复 repeat 次{
    ll a = rand() % (n - 3) + 2;	//选取一个随机数 [2, n - 1)ll x = pow(a, d, n);ll y = 0;for(int j = 0; j < s; ++j){
    y = multi(x, x, n);if(1 == y && x != 1 && x != n - 1)return false;x = y;}if(y != 1)	//费马定理， 不满足费马定理的，就不是素数return false;}return true;
}ll pollard_rho(ll n, ll c)
{
    ll i = 1, k = 2;ll x = rand() % (n - 1) + 1;ll y = x;while(true){
    ++i;x = (multi(x, x, n) + c ) % n;ll d = gcd((y - x + n) % n, n);if(1 < d && d < n)return d;	// d 是n的因子if(x == y)return n;	//找到循环， 返回 n，重新来if(i == k){
    y = x;k <<= 1;}}
}void find(ll n, int c)
{
    	if(1 == n)return;if(Miller_Rabin(n)){
    min_prime = min(min_prime, n);return;}ll p = n, k = c;while(p >= n)p = pollard_rho(p, c--);find(p, k);find(n / p, k);
}int main()
{
    scanf("%d", &T);ll n;while(T--){
    scanf("%lld", &n);if(Miller_Rabin(n)){
    printf("Prime\n");continue;}ct = 0;min_prime = 4e18;find(n, 20);printf("%lld\n", min_prime);}return 0;
}/* 2 5 10 *//* Prime 2 */