题意：求(n-1)！%n，其中t=1e5,n=1e9
做法： 威尔逊定理：n为素数等价于(n-1)！%n=1； 而n为合数时，除了n=4的情况，(n-1)！%n=0；
Miller-Rabin 判别法： 基于 “a^(p-1)%p=1” 和 “若a^2%p=1,则a%p=1或p-1”，随机取10次a验证以上二式是否成立即可。
代码：
#include <bits/stdc++.h> using namespace std; typedef unsigned long long ll; const int T=10; ll exp(ll x, ll y, ll mod){ ll ans=1; ll base=x; while(y){ if(y&1){ ans=ans*base%mod; } y>>=1; base=base*base%mod; } return ans; } 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)){ k++; m>>=1; } for(int i=0;i<T;i++){ ll a=rand()%(n-1)+1; ll x=exp(a, m, n); ll y=0; for(int i=1;i<=k;i++){ y=x*x%n; if(y==1&&x!=1&&x!=n-1)return false; x=y; } if(y!=1)return false; } return true; } int main() { srand(time(NULL)); int t; scanf("%d", &t); while(t--){ ll num; scanf("%llu", &num); if(num==4){printf("2\n");continue;} if(miller_rabin(num))printf("%llu\n", num-1); else printf("0\n"); } }