大致题意
给定一个质数p ，求这个质数的前一个质数 q，输出 q！% p； 1e10 <= p <= 1e14
思路
因为有这么个定理 n 以内的质数的个数趋近 n/ln(n) 所以质数的密度是logn级别的。因此可以暴力的往前找，然后用Miller_Rabin判一下素数，（然后比赛中我是oeis的） 然后由威尔逊定理可以推出计算 q! %p。 参考博客的：https://blog.csdn.net/qq_40791842/article/details/97697165
长见识了…
代码
#include <cstdio>
#include <cstring>
#include<set>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<ctime>
#include<assert.h>
using namespace std
;
#define inf 0x3f3f3f3f
#define maxn 32505
#define sc(x) scanf("%lld",&x)
typedef long long ll
;
const int S
=8;
ll
mul_mod(ll a
,ll b
,ll c
){
a
%=c
;
b
%=c
;
ll ret
=0;
ll temp
=a
;
while(b
){
if(b
&1){
ret
+=temp
;
if(ret
>c
)ret
-=c
;
}
temp
<<=1;
if(temp
>c
)temp
-=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
=mul_mod(ret
,temp
,mod
);
temp
=mul_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
=mul_mod(ret
,ret
,n
);
if(ret
==1&&last
!=1&&last
!=n
-1)return true;
last
=ret
;
}
if(ret
!=1)return true;
else return false;
}
bool Miller_Rabin(ll n
){
if(n
<2)return false;
if(n
==2)return true;
if((n
&1)==0)return false;
ll x
=n
-1;
ll t
=0;
while((n
&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 false;
}
return true;
}
ll
fastpow(ll x
,ll y
,ll p
){
ll ans
,res
;
ans
=1;res
=x
;
while(y
){
if(y
&1)ans
=mul_mod(ans
,res
,p
);
res
=mul_mod(res
, res
, p
);
y
>>=1;
}
return ans
;
}
int main(){
ll t
;sc(t
);
while(t
--){
ll n
;sc(n
);
ll ans
=1;
for(ll i
=n
-2;i
>=1;i
--){
if(Miller_Rabin(i
)){
printf("%lld\n",fastpow(ans
,n
-2,n
));
break;
}else{
ans
=mul_mod(ans
,i
,n
);
}
}
}
}
