用于对较大(int64)范围内的数判定质数。
原理:费马小定理,二次探测定理。
二次探测定理:若 $ p $ 为奇素数且 $ x ^ 2 \equiv1 ( mod \ p ) $ ,则 $ x \equiv \pm1(mod \ p) $ 。
选取多个素数 $ p $ 对要判断的数 $ x $ 进行测试:
首先进行费马小定理判断 $ x^{p-1} \equiv 1 (mod \ p) $ ,不是的话返回非。
之后设 $ k=p-1 $ 。当 $ k $ 是 $ 2 $ 的倍数时,将 $ k $ 除以 $ 2 $ ,继续计算 $ x^{k} \equiv \pm 1 (mod \ p) $ 。
不是的话返回非,否则如果结果为 $ 1 $ 且 $ 2 | k $ ,则继续重复操作,否则当 $ x^{k} \equiv -1 (mod \ p) $ 或 $ k $ 不再可除,无法继续用这个质数进行判定,返回真。
质数表随便打个,我用的 $ 2,3,7,19,61,24251 $ 。
对于分解一个大合数 $ n $ ,考虑每次随机找到一个约数 $ c $ ,将 $ n/c $ 和 $ c $ 两部分递归处理。
随机一个初始变化率 $ d $ 和一个初始值 $ a_{0} $ ,每次 $ a_{i} = ( a_{i-1}^{2} +d ) mod \ n $ 。
每次求 $ gcd( | a_{i} - a_{0} | , n) $ ,如果结果不为 $ 1 $ 或 $ n $ ,那么证明分解出了一个约数。
$ a $ 最终会成环,期望长度 $ \sqrt{n} $ ,成环时更换变化率重新计算即可。
但依然需要继续优化。
考虑路径倍长,统计 $ s = \prod { | a_{i} - a_{0} | } $,每隔 $ 2^{k} $ 次将 $ s $ 一起gcd,之后将 $ a_{0} $ 设置为 $ a_{ k^{ 2 } } $ 。
#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef __int128 llint;
struct pat{int x,y;pat(int x=0,int y=0):x(x),y(y){}bool operator<(const pat &p)const{return x==p.x?y<p.y:x<p.x;}};
template<typename TP>inline void read(TP &tar)
{
TP ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){ret=ret*10+(ch-'0');ch=getchar();}
tar=ret*f;
}
namespace RKK
{
lint fpow(lint a,lint p,lint mo){lint ret=1;while(p){if(p&1ll) ret=(llint)ret*a%mo;a=(llint)a*a%mo,p>>=1;}return ret;}
lint gcd(lint a,lint b){return b?gcd(b,a%b):a;}
lint base[6]={2,3,7,19,61,24251};
bool mr(lint n,lint bas)
{
if(fpow(bas,n-1,n)!=1) return 0;
lint p=n-1;
while(!(p&1))
{
p>>=1;lint g=fpow(bas,p,n);
if(g==n-1) return 1;
else if(g!=1ll) return 0;
}
return 1;
}
bool mr(lint n)
{
if(n<2) return 0;
for(int i=0;i<6;i++)if(n==base[i]) return 1;
for(int i=0;i<6;i++)if(!mr(n,base[i])) return 0;
return 1;
}
lint pr(lint n)
{
int i=1,len=1;lint p=1,d=rand()%(n-1)+1,x=0,y=0;
while(1)
{
x=((llint)x*x+d)%n;
p=(llint)p*abs(x-y)%n;
if(!(i&127)){lint g=gcd(p,n);if(g>1) return g;}
if(i==len)
{
lint g=gcd(p,n);if(g>1) return g;
y=x,p=1,len<<=1,i=1;
}else i++;
}
}
vector<lint> ans;
void getfactor(lint n,vector<lint> &fac)
{
if(n==1ll) return;if(mr(n)){fac.push_back(n);return;}
lint p=n;while(p>=n) p=pr(n);
getfactor(p,fac),getfactor(n/p,fac);
}
int main()
{
int TAT;llint n;read(TAT);while(TAT--)
{
srand(time(NULL));
ans.clear();
read(n);getfactor(n,ans),sort(ans.begin(),ans.end());
if(ans.size()==1) puts("Prime");
else printf("%lld\n",ans[ans.size()-1]);
}
return 0;
}
}
int main(){return RKK::main();}
不知道(?)
手机扫一扫
移动阅读更方便
你可能感兴趣的文章