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)
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
Source
Recommend
代码：
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<queue> #include<stack> #include<set> #include<map> #include<vector> #include<cmath> typedef long long ll; using namespace std; int prime[10000005]; bool vis[10000005]; int cnt =0; void erla() { memset(vis,false,sizeof(vis)); memset(prime,0,sizeof(prime)); for(int t=2; t<=10000003; t++) { if(!vis[t]) { prime[cnt++]=t; } for(int j=0; j<cnt&&t*prime[j]<=10000003; j++) { vis[t*prime[j]]=true; if(t%prime[j]==0) { break; } } } } inline ll ksc(ll x,ll y,ll mod) { return (x*y-(ll)((long double)x/mod*y)*mod+mod)%mod; } ll ksm(ll x,ll y,ll mod) { ll ans=1; while(y) { if(y&1) { ans=ksc(ans,x,mod); } x=ksc(x,x,mod); y>>=1; } return ans; } bool isprime(ll x) { for(int t=0;t<cnt&&prime[t]<x;t++) { if(x%prime[t]==0) { return false; } } return true; } int main() { int T; cin>>T; erla(); while(T--) { ll n; scanf("%lld",&n); ll ans=1; for(ll t=n-2;t>=2;t--) { if(isprime(t)) { break; } ans=ksc(ans,ksm(t,n-2,n),n); //cout<<ans<<endl; } printf("%lld ",ans); } return 0; }