作用:大整数质因数分解
暴力太慢了,于是有大佬发明了这个
Gcd
一个合数一定有一个质因子小于(sqrt{n}),所以 n 至少存在(sqrt{n})个数与 n 有大于 1 的公约数
随机生成
(x=rand(),c=rand()) 随机生成一对数,然后(y=x,x=x^2+c,g=gcd(|y-x|,n)) 经过测试发现 (g>1) 的概率接近 (n^{frac{1}{4}})
具体好像是生日悖论,本蒟蒻不懂。
判环
注意可能会出现环,即出现出现了的数,所以需要判定
用倍增思想,y 现记下 x 的位置,然后 x 跑当前次数一倍的次数。
跑完了之后 y 再记下 x 的位置,次数再翻倍,当 x 等于 y 时,遇到环了
优化
这样应该会 TLE ,经过观察会发现 Gcd 带的 log 很拖时间
若(|y-x|)有和 n 的公约数,那么若干个(|y-x|)乘在一起并取余 n 也有和 n 的公约数
可以用 z 来累计(|y-x|)的乘积,过 127 次在来 Gcd
至于为什么是 127 次,,玄学
注意
- 可能不用 127 次就遇到环了,由于上面打了倍增,可以再生成了许多次时判环。
- z 为 0 时没必要继续
分解
- 若 n 时质数(用 Miller-Rabin ),直接返回
- Pollard Rho 求出一个非平凡因子
- 把非平凡因子消掉,继续分解
Code
Luogu P4718
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef long double LD;
inline LL Abs(LL x) { return x<0?-x:x; }
inline LL Mul(uLL x,uLL y,LL p) { return (x*y-(uLL)((LD)x/p*y)*p+p)%p; }
inline LL Pow(LL x,LL y,LL p){
register LL res=1;
for(;y;y>>=1,x=Mul(x,x,p))
if(y&1)res=Mul(res,x,p);
return res;
}
inline bool Mr(LL n,LL p) {
if(Pow(p,n-1,n)!=1)return 0;
register LL q=n-1,o;
while(!(q&1)) {
q>>=1,o=Pow(p,q,n);
if(o!=1 && o!=n-1)return 0;
if(o==n-1)return 1;
}
return 1;
}
inline bool Prime(LL n) {
if(n<2)return false;
if(n==2||n==3||n==5||n==7||n==43)return true;
return Mr(n,2)&&Mr(n,3)&&Mr(n,5)&&Mr(n,7)&&Mr(n,43);
}
inline LL Gcd(LL x,LL y) {
return y?Gcd(y,x%y):x;
}
inline LL Rho(LL n) {
LL x,y,z,c,g;
register int p,q;
for(;;) {
x=y=rand()%n,c=rand()%n;
p=0,q=z=1;
while(++p) {
x=(Mul(x,x,n)+c)%n;
z=Mul(z,Abs(y-x),n);
if(x==y || !z)break;
if(!(p%127) || p==q) {
g=Gcd(z,n);
if(g>1)return g;
if(p==q)q<<=1,y=x;
}
}
}
}
LL ans;
inline void Dfs(LL n) {
if(n<=ans)return;
if(Prime(n)) { ans=n; return; }
LL p=Rho(n);
while(n%p==0)n/=p;
Dfs(p),Dfs(n);
}
int main() {
srand(20080816);
LL n,T;
scanf("%lld",&T);
while(T--) {
scanf("%lld",&n);
ans=0;Dfs(n);
if(ans==n)puts("Prime");
else printf("%lld
",ans);
}
return 0;
}