题目链接
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 )
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)
For each testcase, output an integer representing the factorial of Q modulo P.
数论题，首先我们要想到素数间隔 上面是素数间隔的百度百科，由此可知， [ 0 , 1 0 18 ] [0,10^{18}] [0,1018] 的素数平均间隔非常小，所以我们对一个数 p p p，可以直接暴力找小于它的素数~ 判定素数目前最快的就是 Miller-Rabin 算法，可以在 O ( k ∗ l o g 2 n ) O(k*log_2^n) O(k∗log2n) 内判断一个素数，下面就考虑阶乘取模，素数阶乘用到了一个数论定理——威尔逊定理： 当 且 仅 当 p 为 素 数 时 ： ( p − 1 ) ! ≡ − 1 ( m o d p ) 当且仅当p为素数时：( p -1 )! ≡ -1 (\ mod\ p ) 当且仅当p为素数时：(p−1)!≡−1( mod p) 我们在此基础上推导： ( p − 1 ) ! ≡ − 1 ( m o d p ) ( p -1 )! ≡ -1 (\ mod\ p ) (p−1)!≡−1( mod p) ( p − 1 ) ! ≡ ( p − 1 ) ( m o d p ) ( p -1 )! ≡ (p-1) (\ mod\ p ) (p−1)!≡(p−1)( mod p) ( p − 2 ) ! ≡ 1 ( m o d p ) ( p -2 )! ≡ 1 (\ mod\ p ) (p−2)!≡1( mod p) ( p − 2 ) ! ≡ 1 ( m o d p ) ( p -2 )! ≡ 1 (\ mod\ p ) (p−2)!≡1( mod p) 1 ≡ 1 ( p − 2 ) ! ( m o d p ) 1 ≡ \frac{1}{(p-2)!} (\ mod\ p ) 1≡(p−2)!1( mod p) q ! ≡ q ! ( p − 2 ) ! ( m o d p ) q! ≡ \frac{q!}{(p-2)!} (\ mod\ p ) q!≡(p−2)!q!( mod p) q ! ≡ 1 ∏ q + 1 p − 2 ( m o d p ) q! ≡ \frac{1}{\prod_{q+1}^{p-2}} (\ mod\ p ) q!≡∏q+1p−21( mod p) 那么答案就很明显了，注意累乘时用上快速乘，因为模数大于 i n t int int，直接乘可能会 WA，AC代码如下：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int S = 8; ll mult_mod (ll a,ll b, ll c) { a%=c,b%=c; ll ret = 0; ll tmp = a; while (b) { if (b&1) { ret += tmp; if (ret > c) ret -= c; } tmp<<=1; if (tmp>c) tmp-=c; b>>=1; } return ret; } ll pow_mod(ll a,ll n,ll mod) { ll ret = 1; ll temp = a%mod; while (n) { if (n&1) ret = mult_mod(ret,temp,mod); temp = mult_mod(temp,temp,mod); n>>=1; } return ret; } bool check(ll a,ll n,ll x,ll t) { ll ret = pow_mod(a,x,n); ll last = ret; for (int i = 1; i <= t; ++i) { ret = mult_mod(ret,ret,n); if (ret == 1&&last!=1&&last!=n-1) return 1; last = ret; } if (ret != 1) return 1; else return 0; } bool MR(ll n) { if(n < 2) return 0; if (n == 2) return 1; if ((n&1)==0) return 0; ll x = n - 1; ll t = 0; while ((x&1)==0) { x>>=1; ++t; } srand(time(NULL)); for (int i = 0; i < S; ++i) { ll a = rand()%(n-1) + 1; if (check(a,n,x,t)) return 0; } return 1; } ll f(ll a,ll b,ll mod) { ll k=0; while(b) { if(b&1) k=(k+a)%mod; a=(a+a)%mod; b>>=1; } return k; } int main(){ ll t,mod,ans,p,q; scanf("%lld",&t); while(t--){ scanf("%lld",&p); mod=p; q=p-1; ans=1; while(!MR(q)) q--; for(ll i=q+1;i<=p-2;i++) ans=f(ans,pow_mod(i,mod-2,mod),mod); printf("%lld\n",ans); } }