即:当且仅当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<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 }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)