傳送門 題目要求求出phi(m!)*(n!/m!) 注意到phi(m!)=m!*(p-1)/p（p是m！的質因子），模數固定。 所以答案就是n！*(p-1)/p（p是m！的質因子） n!可以在線性時間內求出，（p-1）/p（p是m！的質因子）也可以用線性篩求出。 本題略卡時限。 注意：1.10000000以內質數僅有不到500000個，我們可以用遞歸求逆元加速運算。 2.采用某些松松松的技巧可以避免超時。
#include<iostream>#include<cstdio>#define ll long long#define M 10000000using namespace std;int f[M+5];ll n,mo,x,y,p[M+5],q[M+5];int u,v;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;}ll inv(int x){ return (p[x])?p[x]:p[x]=(mo-mo/x)*inv(mo%x)%mo;}int main(){ n=read(); mo=read(); f[1]=p[1]=q[1]=p[0]=1; for (int i=2;i*i<=M;++i) if (!f[i]) for (int j=i*i;j<=M;j+=i) f[j]=1; for (ll i=2;i<=M;++i) q[i]=(f[i])?q[i-1]:q[i-1]*(i-1)%mo*inv(i%mo)%mo; p[1]=1; for (ll i=2;i<=M;++i) p[i]=p[i-1]*i%mo; while (n--){ x=read(); y=read();新聞熱點
疑難解答
