HDU-6608 Fansblog（威尔逊定理+素数间隔+逆元）

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 const int maxn=1e7+10;
 8 ll mod;
 9 int prime[maxn+10],cnt;
10 int vis[maxn+10];
11 void get_prime()
12 {
13     cnt=0;
14     for(int i=2;i<=maxn;++i)
15     {
16         if(!vis[i])
17             prime[cnt++]=i;
18         for(int j=0;j<cnt&&(ll)i*prime[j]<=maxn;j++)
19         {
20             vis[i*prime[j]]=1;
21             if(i%prime[j]==0) break;
22         }
23     }
24 }
25 bool is_prime(ll x)
26 {
27     for(int i=0;i<cnt&&(ll)prime[i]*prime[i]<=x;++i)
28     {
29         if(x%prime[i]==0)
30             return 0;
31     }
32     return 1;
33 }
34 ll mul(ll a,ll b)
35 {
36     ll res=0;
37     while(b)
38     {
39         if(b&1) res=(res+a)%mod;
40         a=(a+a)%mod;
41         b>>=1;
42     }
43     return res%mod;
44 }
45 ll poww(ll a,ll b)
46 {
47     ll res=1;
48     while(b)
49     {
50         if(b&1)
51             res=mul(res,a);
52         a=mul(a,a);
53         b>>=1;
54     }
55     return res;
56 }
57 int main()
58 {
59     int t;
60     ll p,q;
61     get_prime();
62     scanf("%d",&t);
63     while(t--)
64     {
65         scanf("%lld",&p);
66         mod=p;
67         q=p-1;
68         while(!is_prime(q)) q--;
69         ll ans=p-1;
70         for(ll i=q+1;i<=p-1;++i)
71         {
72             ans=mul(ans,poww(i,mod-2));
73         }
74         printf("%lld\n",ans);
75     }
76     return 0;
77 }