填坑……链接：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> 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 ",fac[n]*ans[m]%p); 42 } 43 } 44 int sb=haha(); 45 int main(){;}