参考博客：https://blog.csdn.net/birdmanqin/article/details/97750844

题目链接：链接：http://acm.hdu.edu.cn/showproblem.php?pid=6608

威尔逊定理：在初等数论中，威尔逊定理给出了判定一个自然数是否为素数的充分必要条件。
即：当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )，但是由于阶乘是呈爆炸增长的，其结论对于实际操作意义不大。

题意：T组样例。每组样例，给出一个素数P(1e9≤P≤1e14)，Q是P的前一个素数求Q！%P。

思路：由威尔逊定理得：(P-1)!mod P=-1，即(P-1)!mod P=P-1又因为，
(Q!)*(Q+1)*(Q+2)*…*(P-1)=(p-1)!
得到Q!(mod P)=(((P-1)!)/(Q+1)*(Q=2)*(Q+3)*…*(P-1))(mod P)

又因为威尔逊定理,所以(P-1)!mod P==P-1
Q!(mod P)=((P-1)/(Q+1)*(Q=2)*(Q+3)*…*(P-1))(mod P)

因为两个素数之间的间隔不会超过300,我们从P-1开始一个个查验找Q。再把（P-1）乘上[Q,P-1]的逆元即可。注意因为数很大，所有涉及乘的地方都要用快速乘。

代码：

1 #include
2 #include
3 #include
4 #include
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>=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 }