[SDOI2008]沙拉公主的困惑

题意

求\([1,n!]\)以内与\(m!\)互质的数的个数，答案对\(mod\)取模

思路

由欧几里得定理可知，对于\(x>m!\)，有\(gcd(x,m!)=gcd(x\% m!,m!)\)，所以只需要求出\(m!\)以内的与它互质的数即可，这个数为\(\varphi(m!)\)

所以答案为\(\frac{n!}{m!}*\varphi(m!)\)

本题细节很多啊qwq

Code

//有坑 1 3 4 3
#include<bits/stdc++.h>
#define N 10000005
#define re register
#define Min(x,y) ((x)<(y)?(x):(y))
using namespace std;
typedef long long ll;
int T,n,m;
int p[N],jc[N],inv[N],ans[N],cnt;
bool isnotp[N];
ll mod;

template <class T>
void read(T &x)
{
    char c;int sign=1;
    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
ll quickpow(ll a,ll b)
{
    ll ret=1;
    while(b)
    {
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}
void init(int maxn)
{
    isnotp[1]=1;
    for(re int i=2;i<=maxn;++i)
    {
        if(!isnotp[i]) p[++cnt]=i;
        for(re int j=1;j<=cnt&&(ll)p[j]*i<=maxn;++j)
        {
            isnotp[p[j]*i]=1;
            if(i%p[j]==0) break;
        }
    }
    jc[0]=1; for(re int i=1;i<=maxn;++i) jc[i]=1ll*jc[i-1]*i%mod;
    inv[0]=inv[1]=1; for(re int i=2;i<=maxn;++i) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
    ans[0]=ans[1]=1; for(re int i=2;i<=maxn;++i) ans[i]=(isnotp[i] ? ans[i-1] : 1ll*ans[i-1]*(i-1)%mod*inv[i]%mod);
}
int main()
{
    read(T);read(mod);
    init(N-5);
    while(T--)
    {
        read(n);read(m);
        if(n>=mod&&m<mod) puts("0");
        else printf("%lld\n",(ll)jc[n]*ans[m]%mod);
    }
    return 0;
}