#include #include #include #include const int Times=10; using namespace std; typedef long long LL; LL multi(LL a,LL b,LL m) { LL ans=0; while(b) { if(b&1) { ans=(ans+a)%m; b--; } b>>=1; a=(a+a)%m; } return ans; } LL quick_mod(LL a,LL b,LL m) { LL ans=1; a%=m; while(b) { if(b&1) { ans=multi(ans,a,m); b--; } b>>=1; a=multi(a,a,m); } return ans; } bool Miller_Rabin(LL n) { if(n==2) return true; if(n<2||!(n&1)) return false; LL a,m=n-1,x,y; int k=0; while((m&1)==0) { k++; m>>=1; } for(int i=0;i