题意：求中
互质的数的个数，其中
。
分析：因为，所以
，我们很容易知道如下结论
对于两个正整数和
，如果
是
的倍数，那么
中与
互素的数的个数为
本结论是很好证明的，因为中与
互素的个数为
，又知道
，所以
结论成立。那么对于本题，答案就是
事实上只要把素数的逆元用exgcd求一求就好，其余并未用到
逆元递推法：
#include<stdio.h>
#include<string.h>
const int N=1e7+;
typedef long long ll;
int pr[N],p[N],cnt,mod;
int inv[N],ans1[N],ans2[N];
int read()
{
int x=;char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x;
}
void init(){
ans1[]=ans2[]=inv[]=;
for(int i=;i<N;i++){
ans1[i]=(ll)ans1[i-]*i%mod;
if(!p[i])
pr[++cnt]=i;
for(int j=;j<=cnt&&i*pr[j]<N;j++){
p[pr[j]*i]=;
if(i%pr[j]==) break;
}
}
for(int i=;i<N&&i<mod;i++){
inv[i]=(mod-(ll)mod/i)*inv[mod%i]%mod;
}
for(int i=;i<N;i++){
ans2[i]=ans2[i-];
if(!p[i])
ans2[i]=(ll)ans2[i]*(i-)%mod*inv[i%mod]%mod;
}
}
int main(){
int t,n,m;
scanf("%d%d",&t,&mod);
init();
while(t--){
n=read();m=read();
printf("%d\n",(ll)ans1[n]*ans2[m]%mod);
}
return ;
}
扩展欧几里德求逆元
#include<stdio.h>
#include<string.h>
const int N=1e7+;
typedef long long ll;
int pr[N],p[N],cnt,mod;
int inv[N],ans1[N],ans2[N];
int read()
{
int x=;char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x;
}
int ex_gcd(int a,int b,int &x,int &y){
if(!b){
x=,y=;
return a;
}
int ans=ex_gcd(b,a%b,y,x);
y-=a/b*x;
return ans;
}
int getinv(int i){
int x,y;
ex_gcd(i,mod,x,y);
x=((x%mod)+mod)%mod;
return x;
}
void init(){
ans1[]=ans2[]=inv[]=;
for(int i=;i<N;i++){
ans1[i]=(ll)ans1[i-]*i%mod;
if(!p[i])
pr[++cnt]=i,inv[i]=getinv(i);
for(int j=;j<=cnt&&i*pr[j]<N;j++){
p[pr[j]*i]=;
if(i%pr[j]==) break;
}
}
for(int i=;i<N;i++){
ans2[i]=ans2[i-];
if(!p[i])
ans2[i]=(ll)ans2[i]*(i-)%mod*inv[i%mod]%mod;
}
}
int main(){
int t,n,m;
scanf("%d%d",&t,&mod);
init();
while(t--){
n=read();m=read();
printf("%d\n",(ll)ans1[n]*ans2[m]%mod);
}
return ;
}