题意：
求([1,n!])范围内与(m!)互质的数的个数，多组数据，答案对(R)取模
范围&性质: (1le mle nle 10^7,1le tle 10^4,R)一定是质数
分析：
题目要求得到的其实就是
[sum_{i=1}^{n!}[gcd(i,m!)==1]
]
由于(gcd(x,y)=1)可以推得(gcd(x+ky,y)=1),并且题目保证(mle n)所以我们将(n!)按照大小为(m!)划分成若干段，然后变换求和上界
[ans= frac{n!}{m!}sum_{i=1}^{m!}[gcd(i,m!)==1]
]
我们发现后边的求和不就是欧拉函数吗？！！！再根据欧拉函数的定义式化简
[ans=frac{n!}{m!} imes m!prod_{i=1}^k frac{p_i-1}{p_i}=n! imes prod_{i=1}^kfrac{p_i-1}{p_i}
]
所以我们只要(O(n))的处理出阶乘和每一个数的(prod_{i=1}^kfrac{p_i-1}{p_i})就可以了
代码：
#include<bits/stdc++.h>
using namespace std;
namespace zzc
{
const int maxn = 1e7+5;
long long p[maxn>>3],ans[maxn],fac[maxn],inv[maxn];
bool vis[maxn];
long long n,m,t,mod,cnt=0;
void init()
{
for(long long i=2;i<=10000000;i++)
{
if(!vis[i])
{
p[++cnt]=i;
}
for(long long j=1;j<=cnt&&i*p[j]<=10000000;j++)
{
vis[i*p[j]]=true;
if(i%p[j]==0) break;
}
}
fac[0]=fac[1]=1;
for(long long i=2;i<=10000000;i++)
{
fac[i]=fac[i-1]*i%mod;
}
inv[0]=inv[1]=1;
for(long long i=2;i<=10000000;i++)
{
inv[i]=inv[mod%i]*(mod-mod/i)%mod;
}
ans[0]=ans[1]=1;
for(long long i=2;i<=10000000;i++)
{
ans[i]=ans[i-1];
if(!vis[i]) ans[i]=ans[i]*(i-1)%mod*inv[i]%mod;
}
}
void work()
{
scanf("%lld%lld",&t,&mod);
init();
while(t--)
{
scanf("%lld%lld",&n,&m);
printf("%lld
",fac[n]*ans[m]%mod);
}
}
}
int main()
{
zzc::work();
return 0;
}