Miller&&Pollard POJ 1811 Prime Test

题目传送门

题意：素性测试和大整数分解， N (2 <= N < 2⁵⁴)。

分析：没啥好讲的，套个模板，POJ上C++提交

收获：写完这题得到模板

代码：

/************************************************
* Author        :Running_Time
* Created Time  :2015-8-28 13:02:38
* File Name     :POJ_1811.cpp
 ************************************************/

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int S = 20;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

/*
	素性测试，Miller_Rabin 随机算法
	可以判断< 2^63的数
	素数：true，合数：false
*/
const int S = 20;									//随机算法判定次数，S越大，判错概率越小

//非递归写法，递归写法可能会爆栈
ll GCD(ll a, ll b)	{
	if (a == 0)	return 1;
	if (a < 0)	a = -a;
	while (b)	{
		ll c = a % b;
		a = b; b = c;
	}
	return a;
}

//计算 (a * b) % p，a，b是long long数，直接相乘可能会溢出
ll multi_mod(ll a, ll b, ll p)	{
	ll ret = 0;
	a %= p;	b %= p;
	while (b)	{
		if (b & 1)	{
			ret += a;
			if (ret >= p)	ret -= p;
		}
		a <<= 1;
		if (a >= p)	a -= p;
		b >>= 1;
	}
	return ret;
}

//计算 a ^ x % p
ll pow_mod(ll a, ll x, ll p)	{
	ll ret = 1;
	a %= p;
	while (x)	{
		if (x & 1)	ret = multi_mod (ret, a, p);
		a = multi_mod (a, a, p);
		x >>= 1;
	}
	return ret;
}

/*
	以a为基,n-1=x*2^t，a^(n-1) = 1(mod n)  验证n是不是合数
	一定是合数返回true, 不一定返回false
*/
bool check(ll a, ll n, ll x, int t)	{
	ll ret = pow_mod (a, x, n);
	ll last = ret;
	for (int i=1; i<=t; ++i)	{
		ret = multi_mod (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 true;
	if (n < 2 || ! (n & 1))	return false;			//偶数或1
	ll x = n - 1;	int t = 0;
	while (! (x & 1))	{
		x >>= 1;	t++;
	}
	for (int i=1; i<=S; ++i)	{
		ll a = rand () % (n - 1) + 1;				//需要cstdlib头文件
		if (check (a, n, x, t))	return false;		//合数
	}
	return true;
}

/*
	大整数分解，Pollard_rho 随机算法
	factorize ()保存质因数在vector
*/
ll Pollard_rho(ll x, ll c)	{
	ll i = 1, k = 2;
	ll a = rand () % x;
	ll b = a;
	while (1)	{
		i++;
		a = (multi_mod (a, a, x) + c) % x;
		ll d = GCD (b - a, x);
		if (d != 1 && d != x)	return d;
		if (b == a)	return x;
		if (i == k)	b = a, k += k;
	}
}

void factorize(ll n, vector<ll> &ret)	{
	if (Miller_Rabin (n))	{						//素数
		ret.push_back (n);	return ;
	}
	ll p = n;
	while (p >= n)	p = Pollard_rho (p, rand () % (n - 1) + 1);
	factorize (p, ret);
	factorize (n / p, ret);
}

int main(void)    {
	srand (time (NULL));
	int T;	scanf ("%d", &T);
	while (T--)	{
		ll n;	scanf ("%I64d", &n);
		if (Miller_Rabin (n))	puts ("Prime");
		else	{
			if (n <= 1)	{
				puts ("-1");	continue;
			}
			vector<ll> ans;
			factorize (n, ans);
			sort (ans.begin (), ans.end ());
			printf ("%I64d
", ans[0]);
			// for (int i=0; i<ans.size (); ++i)	{
			// 	printf ("%I64d%c", ans[i], (i == ans.size ()-1) ? '
' : ' ');
			// }
		}
	}
	
    return 0;
}