伪素数： 如果存在和n互素的正整数a满足a^(n-1)≡1(mod n)，则n是基于a的伪素数。
是伪素数但不是素数的个数是非常非常少的，所以如果一个数是伪素数，那么他几乎是素数。
Miller_Rabbin素数测试：随机选k个a进行a^(n-1)≡1(mod n)测试，如果都满足则判断n是素数。
a^(n-1)%mod用快速幂计算。对于大数相乘（两个大于int的数相乘），中间结果可能溢出，所以需要用快速幂思想进行乘法取模。
Miller_Rabbin的出错率为2^(-k)。
//Miller Rabbin [1,2^63)的内大素数测试 //快速幂思想计算(a*b)%mo,防止中间结果溢出
//当a*b结果在longlong内时请不要用这一函数，否则可能Tle
LL mult(LL a,LL b,LL mo)
{
LL ret=,x=a%mo,y=b%mo;
while(y)
{
if(y&) ret=(ret+x)%mo;
x=(x<<)%mo,y>>=;
}
return ret;
}
//快速幂取模
LL qpow(LL x,LL y,LL mo)
{
LL ret=;
while(y)
{
if(y&) ret=mult(ret,x,mo);
x=mult(x,x,mo),y>>=;
}
return ret;
}
//不断测试a^(x-1)%x=1
bool Miller_Rabbin(LL x)
{
if(x==||x==||x==||x==) return ;
if(x<||x%==||x%==||x%==||x%==) return ;
for(int i=;i<=;i++)
if(qpow(rand()%(x-)+,x-,x)!=)
return ;
return ;
}