Fansblog

Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 3170 Accepted Submission(s): 671

Problem Description

Farmer John keeps a website called ‘FansBlog’ .Everyday , there are many people visited this blog.One day, he find the visits has reached P , which is a prime number.He thinks it is a interesting fact.And he remembers that the visits had reached another prime number.He try to find out the largest prime number Q ( Q < P ) ,and get the answer of Q! Module P.But he is too busy to find out the answer. So he ask you for help. ( Q! is the product of all positive integers less than or equal to n: n! = n * (n-1) * (n-2) * (n-3) *… * 3 * 2 * 1 . For example, 4! = 4 * 3 * 2 * 1 = 24 )

Input

First line contains an number T(1<=T<=10) indicating the number of testcases.
Then T line follows, each contains a positive prime number P (1e9≤p≤1e14)

Output

For each testcase, output an integer representing the factorial of Q modulo P.

Sample Input

1
1000000007

Sample Output

328400734

题意

给出一个素数P，找出小于P的最小素数Q，并计算Q的阶乘对P取模的结果

解决

从P-1开始进行素数检测，因为素数的分布是比较密集的，所以可以用试除法来判断素数。

在找到Q之后，由威尔逊定理可知：当P是素数的情况下，(P-1)! Ξ -1(mod P)

因为求的是Q! mod P，所以我们可以先将(P-1)! mod P求出来的，然后利用除法来计算Q! mod P

Code

 1 #include <bits/stdc++.h>

 2 #define ll long long

 3 #define ull unsigned long long

 4 #define ms(a,b) memset(a,b,sizeof(a))

 5 const int inf=0x3f3f3f3f;

 6 const ll INF=0x3f3f3f3f3f3f3f3f;

 7 const int maxn=1e6+10;

 8 const int mod=1e9+7;

 9 const int maxm=1e3+10;

10 using namespace std;

11 bool check(ll n)

12 {

13     for(ll i=2;i*i<=n;i++)

14         if(n%i==0)

15             return false;

16     return true;

17 }

18 ll modmul(ll A,ll B,ll Mod)

19 {

20     return (A*B-(ll)((long double)A*B/Mod)*Mod+Mod)%Mod;

21 }

22 ll Pow(ll a,ll b,ll c)

23 {

24     ll ans=1;

25     while(b)

26     {

27         if(b&1)

28             ans=modmul(ans,a,c);

29         b>>=1;

30         a=modmul(a,a,c);

31     }

32     return ans;

33 }

34 ll inv(ll a,ll b)

35 {

36     return Pow(a,b-2,b);

37 }

38 int main(int argc, char const *argv[])

39 {

40     #ifndef ONLINE_JUDGE

41         freopen("in.txt", "r", stdin);

42         freopen("out.txt", "w", stdout);

43         srand((unsigned int)time(NULL));

44     #endif

45     ios::sync_with_stdio(false);

46     cin.tie(0);

47     int t;

48     ll p;

49     cin>>t;

50     while(t--)

51     {

52         cin>>p;

53         ll num;

54         for(ll i=p-1;;i--)

55             if(check(i))

56             {

57                 num=i;

58                 break;

59             }

60         ll ans=p-1;

61         for(ll i=num+1;i<=p-1;i++)

62             ans=modmul(ans,inv(i,p),p);

63         cout<<ans<<endl;

64     }

65     #ifndef ONLINE_JUDGE

66         cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;

67     #endif

68     return 0;

69 }

巴特西

HDU 6608：Fansblog（威尔逊定理）