【POJ】1811 Prime Test

题意：求n最小素因子。（n<=2^54）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
const ll lim=1e9;
inline void C(ll &a, ll c) { if(a>=c || a<=-c) a%=c; }
inline ll mul(ll a, ll b, ll c) { if(a<=lim && b<=lim) return a*b%c; ll x=0; for(; b; b>>=1, C(a+=a, c)) if(b&1) C(x+=a, c); return x; }
inline ll mpow(ll a, ll b, ll c) { ll x=1; for(; b; b>>=1, a=mul(a, a, c)) if(b&1) x=mul(a, x, c); return x; }
inline ll rand(ll a, ll b) {
	static const ll M=1e9+7, g=220703118;
	static ll now=1998;
	C(now*=g, M);
	return a+(now*now)%(b-a+1);
}
ll gcd(ll a, ll b) { return b?gcd(b, a%b):a; }
inline ll iabs(ll a) { return a<0?-a:a; }
inline ll PR(ll n, ll c) {
	ll x=rand(0, n-1), y=x, k=2, t;
	for(int i=2; ; ++i) {
		x=mul(x, x, n); x+=c; C(x, n);
		t=gcd(iabs(y-x), n);
		if(t!=1 && t!=n) return t;
		if(y==x) return n;
		if(i==k) y=x, k<<=1;
	}
}
bool check(ll n) {
	if(n==2 || n==3 || n==5 || n==7 || n==11 || n==13) return 1;
	if(n<2 || (n&1)==0 || n%3==0 || n%5==0 || n%7==0 || n%11==0 || n%13==0) return 0;
	ll d=n-1;
	int cnt=0;
	while((d&1)==0) d>>=1, ++cnt;
	for(int i=0; i<20; ++i) {
		ll a=mpow(rand(2, n-1), d, n);
		for(int i=0; i<cnt; ++i) { ll t=a; a=mul(a, a, n); if(a==1 && t!=1 && t!=n-1) return 0; }
		if(a!=1) return 0;
	}
	return 1;
}
ll f[100], ans;
int cnt;
void find(ll n) { //printf("%lld
", n);
	if(check(n)) { 
		f[++cnt]=n; ans=min(ans, n);
		return;
	}
	ll p=n;
	while(p==n) p=PR(n, rand(1, n-1));
	find(p); find(n/p);
}

int main() {
	int T; scanf("%d", &T);
	while(T--) {
		ll n;
		scanf("%lld", &n);
		cnt=0; ans=n;
		find(n);
		if(cnt==1) puts("Prime");
		else printf("%lld
", ans);
	}

	return 0;
}

学习了下Pollard-Rho算法= =复杂度期望为$O(n^{1/4})$

具体不说看算导= =

大概就是用$x=x^2+c pmod{n}$然后判$(y-x, n)$是否=1。其中$y$是第$2^k$个$x$。然后找到一个约数后递归这个约数和n/约数。（$c$和初始的$x$随机= =

然后如果碰到环退出就行了= =（一开始不知道为啥被卡了= =原来乘法爆掉了QAQ写个快速乘啊！！！