SDOI2008 沙拉公主的困惑

题目链接：戳我

显然，如果(n==m)的时候，我们求的是(phi(m))
而现在(n>=m)，那么(n!)一定是(m!)的整数倍，每个(m!)对答案的贡献为(phi(m!))
所以题目转化成求
(frac{n!}{m!}phi(m!))
(=frac{n!}{m!}frac{prod (p_i-1)}{prod p_i})
其中(p_i)是小于m的所有质数（因为如果求(phi(x))，那些(p_i)就是它的质因子，而对于阶乘来说，显然就是小于它的所有质数）
(=n!frac{prod(p_i-1)}{prod p_i})
对于这题的数据范围，显然是每次询问的时间复杂度必须要在(O(logn))及以内，所以我们要将上面的值进行预处理。
不能逆着推这道题的逆元！因为没有保证与模数互质QAQ，所以询问的时候直接快速幂求一下就好了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define MAXN 10000000
using namespace std;
int T,mod,n,m,cnt;
int fn[MAXN+10],fv[MAXN+10],prime[MAXN+10],id[MAXN+10],done[MAXN+10],fc[MAXN+10];
inline int fpow(int x,int y)
{
    int cur_ans=1;
    while(y)
    {
        if(y&1) cur_ans=1ll*cur_ans*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return cur_ans;
}
inline void init()
{
    fc[0]=1;
    done[1]=1;
    for(int i=1;i<=MAXN;i++) fc[i]=1ll*fc[i-1]*i%mod;
    for(int i=2;i<=MAXN;i++)
    {
        if(!done[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=MAXN;j++)
        {
            done[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
    fv[0]=fn[0]=1;
    // for(int i=1;i<=100;i++) printf("prime[%d]=%d
",i,prime[i]);
    for(int i=1;i<=cnt;i++) fv[i]=1ll*fv[i-1]*(prime[i]-1)%mod;
    for(int i=1;i<=cnt;i++) fn[i]=1ll*fn[i-1]*prime[i]%mod;
    for(int i=1;i<=cnt;i++)
        for(int j=prime[i];j<prime[i+1];j++)
            id[j]=i;
    // for(int i=1;i<=100;i++) printf("id[%d]=%d
",i,id[i]);
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    scanf("%d%d",&T,&mod);
    init();
    while(T--)
    {
        scanf("%d%d",&n,&m);
        printf("%lld
",1ll*fc[n]*fv[id[m]]%mod*fpow(fn[id[m]],mod-2)%mod);
    }
    return 0;
}