又调了半天。。。后来发现自己求逆元时忘开long long。。。一堆负数qwq。
简而言之，题意就是求φ(m!)*n!/m!，且在mod R意义下。
我们可以化简一下式子： φ(m!)*n!/m!=m!*Π(p-1)/p*n!/m!=n!*Π(p-1)/p,其中p为m!的质因子
求质因子时，因为构成m!=1*2*3*...*m，所以最大质因子不可能比m大；
所以预处理出1-10000000中的质数和逆元。
因为是要mod R，所以求n!时取模，并且一旦为0，后面的一定也都为0，可以省一定时间；
然后求ans时要利用上一个递推过来。
然后记着有些地方要开long long寄存器。
#include<cstdio> #include<iostream> #define R register int const int N=1E+7; using namespace std; inline int g() { R ret=0; register char ch; while(!isdigit(ch=getchar())) ; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret; } int mod,cnt,t,n,m; int pri[N>>2],Inv[N+10],jc[N+10],ans[N+10]; bool v[N+10]; inline void PRE() { for(R i=2;i<=N;++i) { if(!v[i]) pri[++cnt]=i; for(R j=1;j<=cnt&&i*pri[j]<=N;++j) {v[i*pri[j]]=true; if(i%pri[j]==0) break;} }jc[1]=1; for(R i=2;i<=N&&jc[i-1]!=0;++i) jc[i]=(long long)jc[i-1]*i%mod;//,cout<<jc[i]<<" "; Inv[1]=1; for(R i=2;i<=N&&i<mod;++i) Inv[i]=(long long)(mod-mod/i)*Inv[mod%i]%mod;//,cout<<Inv[i]<<endl; ans[1]=1; for(R i=2;i<=N;++i) { ans[i]=ans[i-1]; if(!v[i]) ans[i]=(long long)ans[i]*(i-1)%mod*Inv[i%mod]%mod; } } signed main() { t=g(),mod=g(); PRE(); while(t--) { n=g(),m=g(); printf("%d ",(long long)jc[n]*ans[m]%mod); } }
2019.05.14