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

HDU-6608 Fansblog（威尔逊定理+素数间隔+逆元） 参考博客：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<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 }