C++(g++ 7.5.0) 解法, 执行用时: 594ms, 内存消耗: 126984K, 提交时间: 2023-07-11 19:13:30

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e7+7;
bitset<N>vs;
int T,n=1e7+2,jc[N],s1[N],nv[N],m,M;
int pm[N],pt,sf[N],s2[N];
int main(){
	ios::sync_with_stdio(false);
	int i,j,k,l,r,x,y;
	cin>>T>>M;
	for(x=jc[0]=sf[0]=1;x<=n;++x){
		k=x,s1[x]=s1[x-1];
		while(!(k%M))k/=M,++s1[x];
		jc[x]=1ll*k*jc[x-1]%M;
	}
	nv[0]=nv[1]=1,n=min(n,M-1);
	for(x=2;x<=n;++x)
		nv[x]=ll(M-M/x)*nv[M%x]%M;
	for(x=2;x<=n;++x)
		if(!vs[x]){
			pm[++pt]=x;
			s2[pt]=s2[pt-1];
			sf[pt]=sf[pt-1];
			k=x-1;
			while(!(k%M))k/=M,++s2[pt];
			sf[pt]=1ll*k*sf[pt]%M;
			k=x;
			while(!(k%M))k/=M,--s2[pt];
			sf[pt]=1ll*nv[k%M]*sf[pt]%M;
			for(y=n/x;y>1;--y)vs[x*y]=1;
		}
	while(T--){
		cin>>n>>m;
		m=upper_bound(pm+1,pm+pt+1,m)-pm-1;
		l=1ll*jc[n]*sf[m]%M,r=s1[n]-s2[m];
		printf("%d\n",r?0:l);
	}
	return 0;
}

C++ 解法, 执行用时: 790ms, 内存消耗: 250288K, 提交时间: 2022-01-17 15:19:56

#include<bits/stdc++.h>
using namespace std;
#define int long long
int jc[10000005];
int inv[10000005];
int mod;
int T;
bool ispr[10000005];
int pr[10000005];
int q[10000005];
int sum=0;
int n,m;
signed main(){
cin>>T>>mod;
inv[1]=1;
jc[1]=1;
q[1]=1;
for(int i=2;i<=10000000;i++){
	jc[i]=(jc[i-1]*i)%mod;
	if(i<mod)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	else inv[i]=inv[i%mod];
	q[i]=q[i-1];
	if(!ispr[i]){
		pr[++sum]=i;
		q[i]=(q[i]*(i-1))%mod;
		q[i]=(q[i]*inv[i])%mod;
	}
	for(int j=1;j<=sum&&i*pr[j]<=10000000;j++){
		ispr[i*pr[j]]=1;
		if(i%pr[j]==0)break;
	}
}
while(T--){
	scanf("%lld %lld",&n,&m);
	int ans=(jc[n]*q[m])%mod;
	printf("%lld\n",ans);
}









	return 0;
}