咱这里把92分(最高分)的Miller-rabin的板子贴出来
```cpp
ll MMul(ll a,ll b,ll mod,ll ans = 0){
for(a%=mod;b;b>>=1){
if(b&1)ans = (ans+a)%mod;
a = (a+a)%mod;
}
return ans;
}
ll MExp(ll a,ll b,ll mod,ll ans = 1){
for(a%=mod;b;b>>=1){
if(b&1)ans = MMul(ans,a,mod);
a = MMul(a,a,mod);
}
return ans;
}
bool Miller_Rabin(ll n,ll u = 0,int t = 0,int s = 10){
if(n == 2)return true;
if(!(n&1)||n<2)return false;
for(u = n-1;!(u&1);u>>=1,t++);
while(s--){
ll x = rand()%(n-1)+1;
x = MExp(x,u,n);
for(int i=0;i<t;i++){
ll y = MMul(x,x,n);
if(y==1 && x!=1 && x!=n-1)return false;
x = y;
}
if(x != 1)return false;
}
return true;
}
```
by revolIA @ 2019-02-08 21:06:38
这得拼人品
by wwlw @ 2019-02-08 21:27:43
@[wwlw](/space/show?uid=83337) qwq那也太惨了吧,可是是t不是wa啊,不明白t是怎么回事
by revolIA @ 2019-02-08 21:38:40
@[revolIA](/space/show?uid=75083) 话说我也没写过
by wwlw @ 2019-02-08 22:13:37
@[wwlw](/space/show?uid=83337) 我知道啦,是爆long long了qwq
by revolIA @ 2019-02-10 15:20:42