这题就是求 (n?1)!  mod  n(n-1)!modn(n?1)!mod n

如果nn$n$为合数，显然答案为0.

如果$n$为素数，那么由威尔逊定理可得答案为 $n?1$

注意有个trick为 $n$ = 4

#include<iostream>
#include<cmath>
#define ll long long 

using namespace std;

int t;
int n,ans;

bool Isprime(int m)
{
    int i,isqrt=(int)sqrt(m);
    bool pd=true;
    if(m==2)pd=true;
    else if(m%2==0)pd=false;
    else 
    for(i=3;i<=isqrt;i+=2){
        if(m%i==0){
            pd=false;
            break;
        }
    }
    return pd;
}

int main()
{
    cin>>t;
    while(t--){
        cin>>n;
        if(n==4)ans=2;
        else if(Isprime(n))ans=n-1;
        else ans=0;
        cout<<ans<<endl;
    }
    return 0;
}

版权声明：本文为博主原创文章，未经博主允许不得转载。