C

题意:
就是给你一个n和m，问你1~n!中与m!互质的数有多少个，然后把个数%p。

思考：
刚开始一看根本没法做，猜猜结论n!/m!不对，有个欧拉函数1~n中和m互质的个数为n/m*(m的欧拉函数),但是这个题数据那么大，没法用。然后就去从简单的方式去推一推式子，发现，与m！互质，也就是和m中的所有质数互质，然后直接求不好求，反过来求。用总的可能性n！减去和m中质数不互质的个数。但是这改怎么求呢。比如 4!-4!/2-4!/3+4!/6,加上6是因为2和3多减了一次6。容斥原理，这是最基础的一中情况，如果把5加进去呢 4!-4!-4!/2-4!/3-4!/5+4!/6+4!/10+4!/15-4!/30，可以发现，dp[i] = -dp[i-1]*i+i+dp[i-1]。dp代表的是容斥的内容。除以某个数就是乘以某个数的逆元。

代码：

int T,n,m,mod;
int va[N];
int fact[N],dp[N];
int prime[N];int ksm(int a, int b)
{int sum = 1;while(b){if(b&1) sum = sum*a%mod;a = a*a%mod;b >>= 1;}return sum%mod;
}void init()
{for(int i=2;i<=M;i++){if(prime[i]) continue;for(int j=2*i;j<=M;j+=i) prime[j] = true;}dp[1] = 0;fact[1] = 1;int sum = 0;for(int i=2;i<=M;i++){fact[i] = fact[i - 1] * i % mod;if(!prime[i]){dp[i] = dp[i-1]-sum;dp[i] %= mod;sum = (sum+ksm(i,mod-2))%mod;dp[i] += (-dp[i-1]*ksm(i,mod-2)%mod+sum)%mod;dp[i] %= mod;}  else dp[i] = dp[i-1];}
}signed main()
{cin>>T>>mod;init();while(T--){cin>>n>>m;int ans = fact[n];ans = (ans-fact[n]*dp[m]%mod+mod)%mod;cout<<ans<<"\n";}return 0;
}

总结：
多多推式子，动手写写。