题目传送门。
题意：求\([1,n!]\)中与\(m!\)互质的数的个数，对质数\(R\)取模，\(n\geq m\)。
答案应该等于\(\frac{n!}{m!}\phi(m!)=\frac{n!}{m!}m!\prod_{p|m!}\frac{p-1}{p}=n!\frac{\prod_{p\leq m}\,p-1}{\prod_{p\leq m}\,p}\)。
这里\(p\)为小于等于\(m\)的质数。
所以我们处理出阶乘，以及质数的乘积和对\(R\)的逆元就能得出答案。
你真的这么想？
naive！simple！
如果\(n\geq R\)，答案一定为\(0\)吗？
可以看看这组数据：
答案为\(2\)，因为\(8\,mod\,3=2\)。
但是\(4!\frac{1\cdot 2}{2\cdot 3}\)呢？\(4!=24\)，而\(24\,mod\,3=0\)，但是答案非\(0\)。
正确的做法是什么？
当\(n\geq R\)时，如果\(m\geq R\)的话，\(n!\)中的因子\(R\)就有可能被分母消掉，我们应该要对\(n\geq R\)的\(n!\)消掉一个\(R\)，对\(m\geq R\)的分母也消掉一个\(R\)。
这样就不会有问题了。
代码如下：
#include<cstdio>
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i<(b);++i)
int T,Mod,n,m;
int primes[], pnum=;
bool isn_prime[];
int pi[],inv[];
int in[],fct[];
int pos[];
void init(){
isn_prime[]=isn_prime[]=;
F(i,,){
if(!isn_prime[i]) primes[++pnum]=i;
for(int j=;j<=pnum&&primes[j]*i<=;++j){
isn_prime[primes[j]*i]=;
if(i%primes[j]==) break;
}
}
inv[]=; for(int i=;i<Mod&&i<=;++i)
inv[i]=1ll*(Mod-Mod/i)*inv[Mod%i]%Mod;
pi[]=; F(i,,pnum) pi[i]=1ll*pi[i-]*(primes[i]-)%Mod;
in[]=; F(i,,pnum) if(primes[i]!=Mod) in[i]=1ll*in[i-]*inv[primes[i]%Mod]%Mod; else in[i]=in[i-];
fct[]=; F(i,,) if(i!=Mod) fct[i]=1ll*fct[i-]*i%Mod; else fct[i]=fct[i-];
F(i,,) if(isn_prime[i]) pos[i]=pos[i-]; else pos[i]=pos[i-]+;
}
int main(){
scanf("%d%d",&T,&Mod);
init();
while(T--){
scanf("%d%d",&n,&m);
if(n>=Mod&&m<Mod) puts("");
else printf("%d\n",1ll*fct[n]*pi[pos[m]]%Mod*in[pos[m]]%Mod);
}
return ;
}