//****************************************************************
// Miller_Rabin 算法进行素数测试
//速度快，而且可以判断 <2^63的数
//****************************************************************
const int S=;//随机算法判定次数，S越大，判错概率越小 LL mult_mod(LL a,LL b,LL mod) //(a*b)%c a,b,c<2^63
{
a%=mod;
b%=mod;
LL ans=;
while(b)
{
if(b&)
{
ans=ans+a;
if(ans>=mod)
ans=ans-mod;
}
a=a<<;
if(a>=mod) a=a-mod;
b=b>>;
}
return ans;
} LL pow_mod(LL a,LL b,LL mod) // a^b%mod
{
LL ans=;
a=a%mod;
while(b)
{
if(b&)
{
ans=mult_mod(ans,a,mod);
}
a=mult_mod(a,a,mod);
b=b>>;
}
return ans;
} //以a为基,n-1=x*2^t a^(n-1)=1(mod n) 验证n是不是合数
//一定是合数返回true,不一定返回false bool check(LL a,LL n,LL x,LL t)
{
LL ret=pow_mod(a,x,n);
LL last=ret;
for(int i=;i<=t;i++)
{
ret=mult_mod(ret,ret,n);
if(ret== && last!= && last!=n-) return true;//合数
last=ret;
}
if(ret!=) return true;
else return false;
} // Miller_Rabin()算法素数判定
//是素数返回true.(可能是伪素数，但概率极小)
//合数返回false; bool Miller_Rabin(long long n)
{
if(n<)return false;
if(n==) return true;
if( (n&)==) return false;//偶数
LL x=n-;
LL t=;
while( (x&)== ) { x>>=;t++;}
for(int i=;i<S;i++)
{
LL a=rand()%(n-)+;//rand()需要stdlib.h头文件
if(check(a,n,x,t))
return false;//合数
}
return true;
}