HDU - 5391Zball in Tina Town

一道威爾遜定理的題

也就是求 (n-1)! % n 的值

根據威爾遜定理很容易得到

當n為素數時，該算式為 n-1

而當n不為素數時，該算式為0（除了4,4的結果是2要特判）

代碼如下：

#include <iostream>
using namespace std;
int main()
{
    int T;
    cin>>T;
    int n;
    while(T--){
        cin>>n;
        bool tag=true;
        for(int i=2;i*i<=n;i++){
                if(!(n%i)){
                    tag=false;
                    break;
                }
            }
        if(tag){
            cout<<n-1<<endl;
        }
        else if(n==4){
            cout<<2<<endl;
        }
        else cout<<0<<endl;
    }
    return 0;
}
           

但是這個時間複雜度有點高 快1s了，如果資料再大很容易逾時

然後如果說用線性素數篩的話，打表1e9 O(n)也會逾時，而且數組開不下;

那麼…就用了一種比較進階的方法，也就是Miller-Rabin素數測試算法，時間複雜度就降下來了。

當然這個算法不一定準确，有可能會判斷錯誤（是以，要多判一些素數，這樣會提高準确度）

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
const int MAX =30;
bool vis[MAX];
int prime[MAX];
int cnt=0;
void ss()
{
    for(int i=2;i<=MAX;i++){
        if(!vis[i])
            prime[cnt++]=i;
        for(int j=0;j<cnt && i*prime[j]<=MAX;j++){
            vis[prime[j]*i]=1;
            if(!(i%prime[j]))
                break;
        }
    }
}
long long quickpower(long long n,long long k,long long mo)
{
    long long ans=1;
    while(k){
        if(k&1){
            ans=ans*n%mo;
        }
        k>>=1;
        n=n*n%mo;
    }
    return ans;
}
long long quickji(long long n,long long k,long long mo){
    int ans = 0;
    while(k){
        if(k&1)
            ans = (ans+n)%mo;
        k>>=1;
        n = (n+n)%mo;
    }
    return ans;
}
bool Miller_Rabin(int x)
{
   if(x<2 || !(x&1))
        return false;
   if(x==2)
        return true;
   int s=0,t=x-1;
   while(!(t&1))
        s++,t>>=1;
   for(int i=0;i<cnt && prime[i]<x;i++){
        int a = prime[i];
        long long b = quickpower(a,t,x);
        for(int j=1;j<=s;j++){
            long long k = quickji(b,b,x); //不開long long 會TLE，注意
            if(k==1 && b!=1 && b!=x-1){
                return false;
            }
            b=k;
        }
        if(b!=1)
            return false;
   }
   return true;
}
int main()
{
    ss();
    int T;
    scanf("%d",&T);
    int n;
    for(int i=0;i<T;i++){
        scanf("%d",&n);
        if(Miller_Rabin(n)){
            printf("%d\n",n-1);
        }
        else if(n==4){
            printf("2\n");
        }
        else printf("0\n");
    }
    return 0;
}