数论果然是硬伤qwq 还是智商上的硬伤
我们来讲两个道理
No.1 求1~i！中与i！互质的数的个数
实际上就是求i!的欧拉函数
有如下递推式：
f[1]=1
if(i为合数) f[i]=f[i-1]*i;
if(i为素数) f[i]=f[i-1]*(i-1);
证明如下
首先我们有个神奇引理。叫做：如果n=p1a1*p2a2*………………*pkak是n的素数幂乘积表达式，那么有
$phi[n]=n*\frac{p1-1}{p1}*\frac{p2-1}{p2}*……*\frac{pk-1}{pk}$
所以说我们的$phi[n!]=n!*\frac{p1-1}{p1}*\frac{p2-1}{p2}*……*\frac{pk-1}{pk}$
那么首先我们知道n!是从1乘到n（废话）
那么注意（敲黑板）phi[n]的质因子就是1到n里的质数对不对
我们现在就把所有的分母约掉
所以phi[n]就变成了(所有合数的乘积)*(所有质数-1的乘积)
于是递推式得证
然后第二个问题，就是如果gcd(a,b)==1，那么gcd(a*k+b,b)=1
这个东西有什么用呢？
我们设n!为mul[n]。
由于n>=m，所以mul[n]>=mul[m]，并且mul[n]一定是mul[m]的整数倍。
这样我们发现$mul[n]=mul[m]*\frac{mul[n]}{mul[m]}$
所以说1到mul[n]中和mul[m]互质的，就等于1~mul[m]中与mul[m]互质的，再乘上$\frac{mul[n]}{mul[m]}$
然后逆元乱搞搞就好了qwq
#include#include #include #include #include #define maxn 10000020inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f;}bool s[maxn];int prime[maxn],tot;int mul[maxn];int f[maxn];long long Pow(long long n,int x,int p){ long long ans=1; while(x){ if(x&1) ans=(ans*n)%(long long)p; n=(n*n)%(long long)p; x>>=1; } return ans;} int main(){ int T=read(),p=read(); s[1]=mul[1]=f[1]=1; for(int i=2;i<=maxn;++i){ if(!s[i]) prime[++tot]=i; for(int j=1;j<=tot&&(long long)prime[j]*i<=maxn;++j){ s[i*prime[j]]=1; if(!(i%prime[j])) break; } } for(int i=2;i<=maxn;++i){ mul[i]=((long long)mul[i-1]*(long long)i)%(long long)p; if(s[i]) f[i]=((long long)f[i-1]*(long long)i)%(long long)p; else f[i]=((long long)f[i-1]*(long long)(i-1))%(long long)p; } while(T--){ int n=read(),m=read(); printf("%lld\n",(long long)(((long long)f[m]*(long long)mul[n])%(long long)p*Pow(mul[m],p-2,p))%p); } return 0;}