https://daniu.luogu.org/problem/show?pid=2155 这个题目信息量蛮大的； 首先一个定理 (x,y)=(x,y-x)//x>y 这个就是gcd啊； 设(x,y)=t; t|x; t|y ∴(x,y-x)=t; 那么 (x,y+k*x)=(x,y) 即
若一个数x与m!互质，那么x+(m!)也一定与m!互质，(x+m!*2)也一定与m!互质 于是我们每存在到一个x<=m!与m!互质，我们就一定能找到(n!)/(m!)个与m!互质的数
所以题目就是让我们求
φ(m!)*(n!)/(m!) %p
这个用通式可以变成
n!*∏(pi-1)/pi
上面选自某犇博客 我们可以离线处理n!，但是我们不能边除边模 所以我们要求逆元； 用exgcd求逆元显然萎了； 那么我们怎么办？ 这里
最后一步
inv[i] == -MOD / i * inv[MOD%i] inv[i] == ( MOD - MOD / i) * inv[MOD%i]
道理和 ((x-y)%mo+mo)%mo 是一样的； 代码
#include<iostream> #include<cstdio> #include<cstring> #define Ll long long using namespace std; const int M=1e7; Ll q[M+5],tot,p[M+5];//为了节约内存，我重复利用q,p数组 bool com[M+5]; Ll m,mo,x,y; int read(){ int k=0; char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()); for (;ch>='0'&&ch<='9';ch=getchar()) k=k*10+ch-48; return k; } void findcom(){ com[1]=1; for(int i=2;i<=M;i++){ if(!com[i]){q[++tot]=i;} for(int j=1;j<=tot;j++){ if(i*q[j]>M)break; com[i*q[j]]=1; if(i%q[j]==0)break; } } } int inv(int x){ if(p[x])return p[x];return p[x]=(mo-mo/x)*inv(mo%x)%mo; } void findinv(){ q[1]=p[0]=p[1]=1; for(int i=2;i<=M;i++)if(com[i])q[i]=q[i-1];else q[i]=q[i-1]*(i-1)%mo*inv(i%mo)%mo; } void find1_N(){ p[1]=1; for(int i=2;i<=M;i++)p[i]=p[i-1]*i%mo; } int main(){ m=read();mo=read(); findcom(); findinv(); find1_N(); while(m--){ x=read();y=read(); printf("%lld\n",p[x]*q[y%mo]%mo); } }大家可以看到我求inv(i)时对i取模； 假如(i>mo) 那么令i=x+y*mo; 那么我们乘inv（i）就等于inv(x)； 这个用exgcd也可以证明
