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为素数时：( p -1 )! ≡ -1 ( mod p )。
在zrz巨巨的指导下，知道了威尔逊定理这个东西。因为素数间隔大概是ln(x)，所以求q的阶乘可以求(p-1)!%p*tmp。这里tmp的含义是q+1~p的所有数的逆元的乘积。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<vector>
#include<bitset>
#include<time.h>
//#define mod (20090717)
using namespace std;
typedef long long ll;
/* ************************************************** Miller_Rabin 算法进行素数测试* 速度快可以判断一个 < 2^63 的数是不是素数***************************************************/
const int S = 8; //随机算法判定次数一般 8 ～ 10 就够了
// 计算 ret = (a*b)%c a,b,c < 2^63
long long mult_mod(long long a,long long b,long long c) {a %= c;b %= c;long long ret = 0;long long 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;
}
// 计算 ret = (a^n)%mod
long long pow_mod(long long a,long long n,long long mod) {long long ret = 1;long long temp = a%mod;while(n) {if(n & 1)ret = mult_mod(ret,temp,mod);temp = mult_mod(temp,temp,mod);n >>= 1;}return ret;
}
// 通过 a^(n ? 1)=1(mod n)来判断 n 是不是素数
// n ? 1 = x ? 2 t 中间使用二次判断
// 是合数返回 true, 不一定是合数返回 false
bool check(long long a,long long n,long long x,long long t) {long long ret = pow_mod(a,x,n);long long last = ret;for(int i = 1; i <= t; i++) {ret = mult_mod(ret,ret,n);if(ret == 1 && last != 1 && last != n - 1)return true;//合数last = ret;}if(ret != 1)return true;else return false;
}
//**************************************************
// Miller_Rabin 算法
// 是素数返回 true,(可能是伪素数)
// 不是素数返回 false
//**************************************************
bool Miller_Rabin(long long n) {if( n < 2)return false;if( n == 2)return true;if( (n&1) == 0)return false;//偶数long long x = n - 1;long long t = 0;while( (x&1)==0 ) {x >>= 1;t++;}srand(time(NULL));/* *************** */for(int i = 0; i < S; i++) {long long a = rand()%(n - 1) + 1;if( check(a,n,x,t) )return false;}return true;
}
int main(){int t;cin>>t;while(t--){ll n;scanf("%lld",&n);ll ans=n-1;for(ll i=n-1;i>=2;i--){if(Miller_Rabin(i)){break;}else{ans=mult_mod(ans,pow_mod(i,n-2,n),n);}}printf("%lld\n",ans);}return 0;
}