素性测试+PollardRho

其实还可以数据小的直接跑暴力，但是没必要。

分解质因数

暴力

还是枚举区间 \([2,\sqrt n]\) 内的数，然后随意弄一下就好了。

std::vector CutbyPrime(ll n){
	static std::vectorans;
	ans.clear();
	for(int i=2;i<=n;++i){
		if(n%i==0){
			while(n%i==0) n/=i;
			ans.push_back(i);
		}
	}
	if(n!=1){
		ans.push_back(n);
	}
	return ans;
}

生日悖论

具体就是说，在一年有 \(365\) 天的情况下，房间中有 \(23\) 个人，至少两个人生日相同的概率达到及以上 \(50\%\) 。

证明可以看 OI wiki ，我就不证啦。

因此大约就是在一年有 \(n\) 天的情况下，房间中有 \(\sqrt n\) 个人，至少两个人生日相同的概率达到及以上 \(50\%\) 。

那么我们选数 \(\sqrt n\) 次得到重复的概率就达到了 \(50\%\) 。

PollardRho

我们发现对于一个非素数的数 \(p\) ，如果有两个数 \(x1,x2\) 和 \(n\) 的一个非平凡因子 \(q\) 满足 \(x1=x2(mod\ q)\) 且 \(x1\not=x2(mod\ p)\)，那么我们可以通过 \(gcd(\lvert x1-x2\rvert,p)\) 求得 \(p\) 的一个非平凡因子。

有了上面的方法，看起来很强，但其实我们根本用不了，所以考虑怎么弄到这个东西。

我们先用一个伪随机函数 \(F(x)=x^2+t\) （\(t\) 为常数） 生成序列 \(f(x)\)，并定义 \(g(x)=f(x)\%q\)。我们由生日悖论可知，\(g(x)\) 期望在 \(O(\sqrt q)\le O(n^{\frac{1}{4} })\) 步内就会出现重复的数，从而出现环（所以形如 \(\rho\) 以此得名）。我们让两个指针错位的在 \(f(x)\) 上跳，然后逐个检验，只要出现一个 gcd 不为 \(1\) 的就返回。

发现 \(gcd\) 带了一个 \(\log\) ，特别难受。但是我们知道 \(gcd(a,p)>1\ or\ gcd(b,p)>1\Leftrightarrow gcd(ab\%p,p)>1\)

，所以我们把一连串的要测试的值乘起来并对 \(p\) 取模， 达到一个上界（一般取 \(128\)）就算一次 gcd，如果满足大于 \(1\) 的条件，那么就对里面元素扫一遍求一下 gcd 找到其中一个可行解即可。

我们有两种错位方法：

1.追及法

设置一个指针步长为 \(1\)，另一个为 \(2\) 即可。

2.倍增法

设置一个指针只取到 \(f_{2^i}\) ，另一个在 \(f_{(2^i,2^{i+1}]}\) 上跳，一个一个判断。

我们给一个倍增法的模板吧。

inline ll PollardRho(ll p){
	ll c=rd()%(p-1)+1;
	ll x,y=0,buf=1;
	int top=0;
	for(int st=1;;st<<=1){
		x=y;
		for(int i=0;i1) break;
				top=0;
			}
		}
		if(top==lim) break;
	}
	for(int i=1;i<=top;++i){
		buf=gcd(sav[i],p);
		if(buf>1) return buf;
	}
	return n;
}

我们每找到一个非平凡因子，就可以继续分治 \(q,n/q\) 。总之就是这样了。

模板题

给一个参考代码：

#include
#define ll long long
#define db double
#define filein(a) freopen(#a".in","r",stdin)
#define fileot(a) freopen(#a".out","w",stdout)
#define sky fflush(stdout);
#define gc getchar
#define pc putchar
namespace IO{
	inline bool blank(const char &c){
		return c==' ' or c=='\n' or c=='\t' or c=='\r' or c==EOF;
	}
	inline void gs(char *s){
		char ch=gc();
		while(blank(ch) ) {ch=gc();}
		while(!blank(ch) ) {*s++=ch;ch=gc();}
		*s=0;
	}
	inline void gs(std::string &s){
		char ch=gc();s+='#';
		while(blank(ch) ) {ch=gc();}
		while(!blank(ch) ) {s+=ch;ch=gc();}
	}
	inline void ps(char *s){
		while(*s!=0) pc(*s++);
	}
	inline void ps(const std::string &s){
		for(auto it:s) 
			if(it!='#') pc(it);
	}
	template
	inline void read(T &s){
		s=0;char ch=gc();bool f=0;
		while(ch<'0'||'9'
	inline void read(T &s,A &...a){
		read(s);read(a...);
	}
};
using IO::read;
using IO::gs;
using IO::ps;
int ts[8]={2,3,5,7,13,19,61,233};
inline ll inc(ll a,ll b,ll c){
	return (a+=b)>=c?a-c:a;
}
inline ll dec(ll a,ll b,ll c){
	return (a-=b)<0?a+c:a;
}
inline ll mul(ll a,ll b,ll c){
	return (__int128)a*b%c;
	/*
	//有时可以考虑龟速乘，但是巨慢，慎用
	ll res=0;
	while(b){
		if(b&1) res=inc(res,a,c);
		a=inc(a,a,c);
		b>>=1;
	}
	return res;
	*/
}
inline ll qpow(ll a,ll b,ll c){
	ll res=1;
	while(b){
		if(b&1) res=mul(res,a,c);
		a=mul(a,a,c);
		b>>=1;
	}
	return res;
}
ll gcd(ll x,ll y){
	if(!x) return y;
	return gcd(y%x,x);
}
inline bool MillerRabin(ll p){
	if(p<=2) return p==2;
	if(!(p&1) ) return 0;
	ll t=p-1;int k=0;
	while(!(t&1) ) {t>>=1;++k;}
	for(int i=0;i<8;++i){
		if(p==ts[i]) return 1;
		ll a=qpow(ts[i],t,p);
		for(int j=0;j1) break;
				top=0;buf=1;
			}
		}
		if(top==128) break;
	}
	for(int i=1;i<=top;++i){
		buf=gcd(sav[i],p);
		if(buf>1) return buf;
	}
	return p;
}
ll mx;
inline void divide(ll p){
	if(p<=mx or p<2) return;
	if(MillerRabin(p) ){
		mx=std::max(mx,p);
		return;
	}
	ll q=PollardRho(p);
	while(p==q) q=PollardRho(p);
	while(p%q==0) p/=q;
	divide(p);divide(q);
}
int main(){
	filein(a);fileot(a);
	int T;read(T);
	while(T--){
		ll n;read(n);
		mx=0;divide(n);
		if(mx==n){
			printf("Prime\n");
		}else printf("%lld\n",mx);
	}
	return 0;
}