题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6608
题目大意：
给定一个素数p，找到比p小的最大素数q，计算q! mod p
解题思路：
这道题有三种方法
第一种(最快)：
先用Miller_Rabin测试找到q，根据威尔逊定理，(p-1)! mod p=p-1有 q! mod p=1/((q+1)(q+2)......(p-2)) mod p
使用费马小定理求逆计算除法取模
第二种(第二快)：
先计算出2~1e7的所有素数，再用找到的素数判定素数找到q，在根据威尔逊定理，依次计算，就可以得到答案
第三种(最慢)：
使用最平常的素数判定方法，即小素数判定方法，时间复杂度O(sqrt(n))，找到q，在使用威尔逊定理、费马小
定理等，就可以得到答案
代码：
第一种：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int N = 1e7+39+7;
ll p,q;
ll quickMul(ll a,ll b,ll m){
ll ans=0;
while(b){
if(b&1)ans=((ans%m)+(a%m))%m;
a=((a%m)+(a%m))%m;
b>>=1;
}
return ans;
}
ll quickPow(ll a,ll b,ll m){
ll ans=1;
while(b){
if(b&1)ans=quickMul(ans,a,m);
a=quickMul(a,a,m);
b>>=1;
}
return ans;
}
bool witness(ll a,ll n,ll u,ll t){
ll x1,x2;
x1=quickPow(a,u,n);
for(ll i=1;i<=t;i++){
x2=quickPow(x1,2,n);
if(x2==1&&x1!=1&&x1!=n-1)return 1;
x1=x2;
}
if(x1!=1)return 1;
return 0;
}
bool Miller_Rabin(ll n){
ll u=n-1,t=0;
while(!(u&1))u>>=1,t++;
if(n<2)return 0;
if(n==2)return 1;
if(n%2==0)return 0;
for(ll i=1;i<=50;i++){
ll a=rand()%(n-1)+1;
if(witness(a,n,u,t))return 0;
}
return 1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--){
ll ans=1;
cin>>p;ans=p-1;
q=p-1;
while(!Miller_Rabin(q))q--;
for(ll i=q+1;i<=p-1;i++)ans=quickMul(ans,quickPow(i,p-2,p),p);
cout<<ans<<'\n';
}
return 0;
}
第二种：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e7+39+7;
ll p,q,cnt=0,prime[N];bool flag[N];
void init(){
memset(flag,0,sizeof(flag));
for(ll i=2;i<=10000000;i++){
if(!flag[i])prime[++cnt]=i;
for(ll j=1;j<=cnt;j++){
if(i*prime[j]>10000000)break;
flag[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
bool is_Prime(ll n){
for(int i=1;i<=cnt&&prime[i]*prime[i]<n;i++){
if(n%prime[i]==0)return 0;
}
return 1;
}
ll quickMul(ll a,ll b,ll m){
ll ans=0;
while(b){
if(b&1)ans=((ans%m)+(a%m))%m;
a=((a%m)+(a%m))%m;
b>>=1;
}
return ans;
}
ll quickPow(ll a,ll b,ll m){
ll ans=1;
while(b){
if(b&1)ans=quickMul(ans,a,m);
a=quickMul(a,a,m);
b>>=1;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
int T;
cin>>T;
while(T--){
ll ans=1;
cin>>p;
q=p-2;
while(!is_Prime(q)){
ans=quickMul(ans,quickPow(q,p-2,p),p);
q--;
}
cout<<ans<<'\n';
}
return 0;
}
第三种：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int N = 1e7+39+7;
ll p,q,cnt=0;
bool is_Prime(ll n){
for(ll i=2;i*i<=n;i++)if(n%i==0)return 0;
return 1;
}
ll quickMul(ll a,ll b,ll m){
ll ans=0;
while(b){
if(b&1)ans=((ans%m)+(a%m))%m;
a=((a%m)+(a%m))%m;
b>>=1;
}
return ans;
}
ll quickPow(ll a,ll b,ll m){
ll ans=1;
while(b){
if(b&1)ans=quickMul(ans,a,m);
a=quickMul(a,a,m);
b>>=1;
}
return ans;
}
bool witness(ll a,ll n,ll u,ll t){
ll x1,x2;
x1=quickPow(a,u,n);
for(ll i=1;i<=t;i++){
x2=quickPow(x1,2,n);
if(x2==1&&x1!=1&&x1!=n-1)return 1;
x1=x2;
}
if(x1!=1)return 1;
return 0;
}
bool Miller_Rabin(ll n){
ll u=n-1,t=0;
while(!(u&1))u>>=1,t++;
if(n<2)return 0;
if(n==2)return 1;
if(n%2==0)return 0;
for(ll i=1;i<=50;i++){
ll a=rand()%(n-1)+1;
if(witness(a,n,u,t))return 0;
}
return 1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--){
ll ans=1;
cin>>p;ans=p-1;
q=p-1;
while(!is_Prime(q))q--;
for(ll i=q+1;i<=p-1;i++)ans=quickMul(ans,quickPow(i,p-2,p),p);
cout<<ans<<'\n';
}
return 0;
}