Miller-Rabin素数判断

このアルゴリズムは線形ふるいのテンプレートを过ごすのは难しいですね.何度も直してやっと単点800 msに引っかかりました.実はこのアルゴリズムは玄学です.ランダム数を取って、ずっとどんな定理で试していますか.それから、间违う确率が非常に小さいと言っていますが、実は间违いますよ.だから、玄学です.一般的に10回やってみるのは保険ですが、実は5回ぐらいで十分です(特にカードの時間の時)実はこのアルゴリズムを学ぶのはpollard-rhoの因数分解を学ぶためです.そうしないと、私はこのような玄学のものを学びに来ますか?私のRPが-infであることを知っておく必要があります..はい、コードをつけます.

#include
#include
#include
#include
#include
#include
#include
#define ll int
using namespace std;
inline int read(){
    int x=0;char ch=' ';int f=1;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')f=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int times=5;
inline ll mul(ll a,ll b,ll p){
    a%=p;b%=p;
    ll ans=0;
    while(b){
        if(b&1){
            ans=(ans+a)%p;
        }
        a=(a+a)%p;
        b>>=1;
    }
    return ans;
}
inline ll ksm(ll a,ll b,ll p){
    a%=p;
    ll ans=1;
    while(b){
        if(b&1){
            ans=mul(ans,a,p);
        }
        a=mul(a,a,p);
        b>>=1;
    }
    return ans;
}
inline bool miller_rabin(ll n){
    if(n==2)return true;
    if(n<2||(!(n&1)))return false;
    ll m=n-1;
    ll k=0;
    while(!(m&1)){
        m>>=1;k++;
    }
    for(int i=1;i<=times;i++){
        ll a=rand()%(n-1)+1;
        ll x=ksm(a,m,n);
        for(int j=1;j<=k;j++){
            ll y=mul(x,x,n);
            if(y==1&&x!=1&&x!=n-1)return false;
            x=y;
        }
        if(x!=1)return false;
    }
    return true;
}
int n,m;
int main(){
    n=read();m=read();
    while(m--){
        int x=read();
        if(miller_rabin(x))printf("Yes
");
        else printf("No
");
    }
    return 0;
}