填坑……链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2186
题意：求出$n!$中与$m!$互质数数目。
这个思路……看完之后仍然难以平静……
首先我们想一想一些小数据就会发现，如果$x$与$m!$不互质，那么$x+km!$也与$m!$不互质。所以结果就是$phi(m!)*n!/m!$,那么我们就可以把这个范围从$n!$缩小至$m!$然而还是没卵用，然后我们可以发现，$m!$的所有质因子，也即$m$内所有质数，于是$phi(m!)=m!*∏((pi-1)/pi)$。那么结果就是$n!*∏((pi-1)/pi)$。这些都是可以预处理的。于是问题得解。
1 #include<iostream>bzoj2186
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 int gcd(int a,int b)
7 {
8 return (!b)?a:gcd(b,a%b);
9 }
10 const int maxn=10000105;
11 bool notprime[maxn];
12 long long prime[500500],ans[maxn],fac[maxn],inv[maxn];
13 int n,m,p,t,tot;
14 void shai()
15 {
16 notprime[0]=notprime[1]=1;
17 for(int i=2;i<=10000000;i++)
18 {
19 if(!notprime[i])prime[++tot]=i;
20 for(int j=1;j<=tot&&prime[j]*i<=10000000;j++)
21 {
22 notprime[i*prime[j]]=1;
23 if(!(i%prime[j]))break;
24 }
25 }
26 fac[1]=1;
27 for(int i=2;i<=10000000;i++)fac[i]=fac[i-1]*i%p;
28 inv[1]=1;
29 for(int i=2;i<=10000000&&i<p;i++)inv[i]=(p-p/i)*inv[p%i]%p;
30 ans[1]=1;
31 for(int i=2;i<=10000000;i++)
32 if(!notprime[i])ans[i]=ans[i-1]*(i-1)%p*inv[i%p]%p;
33 else ans[i]=ans[i-1];
34 }
35 int haha()
36 {
37 scanf("%d%d",&t,&p);shai();
38 while(t--)
39 {
40 scanf("%d%d",&n,&m);
41 printf("%d\n",fac[n]*ans[m]%p);
42 }
43 }
44 int sb=haha();
45 int main(){;}