撰写- 题意
- 给一个质数p（1e9<=p<=1e14）
- 求比p小的最大质数q
- 求q! mod p
- 题解
- 1e14附近的素数密度很大（理论上logn，实际上要更小一些）
- 直接选择暴力筛或者先筛出1e7的质数再以此暴力应该都行
- 由威尔逊顶定理：（p-1）！mod p =1
- 所以q! mod p = 1/((prime(n)+1)*(prime(n)+2)*…*(prime(n+1)-2)) mod prime(n+1) (n>1)
- 求个逆元即可
- 代码
-
#include<algorithm> #include <iostream> #include <fstream> #include <cstdlib> #include <cstring> #include <cassert> #include <cstdio> #include <vector> #include <string> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define P(a,b,c) make_pair(a,make_pair(b,c)) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--) #define CLR(vis) memset(vis,0,sizeof(vis)) #define MST(vis,pos) memset(vis,pos,sizeof(vis)) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef pair<int,pair<int,int> >pii; typedef long long ll; typedef unsigned long long ull; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } template<class T>inline void gmax(T &A, T B) { (A<B)&&(A=B);//if(B>A)A=B; } template<class T>inline void gmin(T &A, T B) { (A>B)&&(A=B);//if(B<A)A=B; } template <class T> inline bool scan_d(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; //EOF while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } inline void outt(int x) { if(x>9) outt(x/10); putchar(x%10+'0'); } bool is_prime(ll x){ for(ll i =2;i*i<=x;i++){ if(x%i==0){ return false; } } return true; } ll p,q; ll q_plus(ll a,ll b){ ll sum=0; while(b){ if(b&1)sum=(sum+a)%p; b/=2; a = (a+a)%p; } return sum; } ll qow(ll a,ll b){ ll sum=1; while(b){ if(b&1)sum=q_plus(sum,a)%p; b/=2; a = q_plus(a,a)%p; } return sum; } int main(){ int t; scanf("%d",&t); while(t--){ //scanf("%I64d", &p); cin>>p; for(ll i=p-1;i>=2;i--){ if(is_prime(i)){ q=i; break; } } ll sum=1; for(ll i=q+1;i<=p-2;i++){ sum = q_plus(sum,i)%p; } //printf("%I64d\n", qow(sum,p-2)%p); cout<< qow(sum,p-2)%p<<endl; } return 0; }
-
叶神版本：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1e7+7;
const int inf = 0x3f3f3f3f;
int prime[maxn+1];
void init()
{
for(LL i=2;i<=maxn;i++)
{
if(!prime[i]) prime[++prime[0]]=i;
for(LL j=1;j<=prime[0] && prime[j]<=maxn/i;j++)
{
prime[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
bool check(LL x)
{
for(int i=1;i<=prime[0] && prime[i]<x;i++)
if(x%prime[i]==0) return false;
return true;
}
LL mulmod(LL a,LL b,LL c)
{
LL res=0;
while(b)
{
if(b&1) res=(res+a)%c;
a=(a+a)%c;
b=b>>1;
}
return res;
}
LL qsm(LL a,LL b,LL c)
{
LL res=1;
while(b)
{
if(b&1) res=mulmod(res,a,c)%c;
a=mulmod(a,a,c)%c;
b=b>>1;
}
return res;
}
int T;
LL P,Q;
int main()
{
init();
/*
for(int i=2;i<=100;i++)
{
LL ans=1;
for(int j=1;j<=prime[i-1];j++)
ans=ans*j%prime[i];
printf("P:%d Q:%d ans:%lld\n",prime[i],prime[i-1],ans);
}
*/
scanf("%d",&T);
while(T--)
{
scanf("%lld",&P);
for(LL i=P-1;;i--)
{
if(check(i))
{
Q=i;
//printf("Q=%lld\n",Q);
LL t=P-Q-1;
LL ans=1;
for(LL k=2;k<=t;k++)
{
//printf("%lld %lld\n",k,qsm(k,P-2,P));
ans=mulmod(ans,qsm(k,P-2,P),P)%P;
}
printf("%lld\n",ans);
break;
}
}
}
return 0;
}