SP288 PON - Prime or Not 题解

XL4453 · 2022-04-12 16:33:42 · 题解

引理：

如果 p 是一个质数，那么 a^2\equiv 1\pmod p 中仅有 a=1 或者 a=p-1 这两组平凡解。

证明是这样的：a^2-1\equiv 0\pmod p 也就是：(a-1)(a+1)\equiv 0 \pmod p，如果 p 是一个素数，那么有：p|a-1 或者 p|a+1。否则一个合数就可能能够拆成两个因数的乘积的形式，例如 a=5，p=24。

根据费马小定理 a^{p-1}\equiv 1\pmod p，将 p-1 写成：2^kt 的形式，其中 t 是一个整数，且 k 尽可能大。

考虑这样的一串数字：a^{2^0t},a^{2^1t},a^{2^2t},...,a^{2^kt}，其中已知 a^{2^kt}=1。由于每一个数都是之前的一个数的平方，所以如果 p 是一个素数，可能的情况只有两种，全都是 1，或者 -1 之后出现了 1。其中，如果没有出现 -1 就直接出现了 1 与引理违背，可以得出 p 一定不是质数的结论。

最后还要求 a^{p-1}，也就是 a^{2^kt}\equiv 1\pmod p。

如果以上的过程都满足了，那么 p 有很大可能性是一个质数，重复几次就几乎能确定是一个质数了。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
int T,n,A[]={2,3,5,7,11,13,17,37,325,9375,28178,450775,9780504,1795265022};
int m(int a,int b,int MOD){
    int ans=0;
    while(b){
        if(b&1)ans=(ans+a)%MOD;
        a=(a+a)%MOD;
        b=b>>1;
    }
    return ans;
}
int pow(int a,int b,int MOD){
    int ans=1;
    while(b){
        if(b&1)ans=m(ans,a,MOD)%MOD;
        a=m(a,a,MOD)%MOD;
        b=b>>1;
    }
    return ans;
}
bool check(int x){
    if(x==2)return 1;
    if(x%2==0)return 0;
    for(auto C:A){
        if(C>=x-1)break;
        if(pow(C,x-1,x)!=1)return 0;
        int a=x-1;
        while(a%2==0){
            a>>=1;
            int u=pow(C,a,x);
            if(u!=1&&u!=x-1)return 0;
            if(u==x-1)break;
        }
    }
    return 1;
}
signed main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);
        if(check(n))printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}