题目大意

求n!中与m!互质的数的个数。

显然的结论

就是求 n!∗Πk|m!k−1k 至于为什么就不说了，太过显然。 然后预处理阶乘，后面那个与m有关可以预处理，为了不超时还要线性求逆。

#include<cstdio> #include<algorithm> #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; typedef long long ll; const int maxn=10000000+10; int inv[maxn],ans[maxn],pri[maxn],fac[maxn]; bool bz[maxn]; int i,j,k,l,t,n,m,now,mo,ca,top; int main(){ scanf("%d%d",&ca,&mo); fac[0]=1; fo(i,1,maxn-10) fac[i]=(ll)fac[i-1]*i%mo; inv[1]=1; fo(i,2,maxn-10) inv[i]=(ll)(mo-mo/i)*inv[mo%i]%mo; ans[1]=1; fo(i,2,maxn-10){ ans[i]=ans[i-1]; if (!bz[i]){ pri[++top]=i; ans[i]=(ll)ans[i]*(i-1)%mo*inv[i]%mo; } fo(j,1,top){ if ((ll)i*pri[j]>maxn-10) break; bz[i*pri[j]]=1; if (i%pri[j]==0) break; } } while (ca--){ scanf("%d%d",&n,&m); now=(ll)fac[n]*ans[m]%mo; printf("%d\n",now); } }