[BZOJ2186][Sdoi2008]沙拉公主的困惑（数论）

题目描述

传送门

题解

首先如果 (a,b)=1 ，则 (a+b,b)=1
因为n>m，所以m!|n!
φ(m!) 表示1~m!中与m!互质的数的个数，那么如果将这些数都加上m!的倍数也一定与m!互质
所以答案为 φ(m!)∗n!m!
把这个式子化简一下
φ(m!)∗n!m!
=m!∏ipi−1pi∗n!m!
=n!∏ipi−1pi
其中 m!=∏ipkii
如果将m!分解质因数的话，所有小于等于m的质因子次数都至少为1，而需要求的这个式子与质因子次数并没有关系，那么直接对所有小于等于m的质因子做就可以了
感觉时间还是有一点点不科学…离线之后预处理一些

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define LL long long
#define N 10000005

int T,maxn,maxm;
int n[10005],m[10005],p[N],prime[1000005],range[N];
LL Mod,ans,phi[1000005],mul[N];

void get(int n)
{
    for (int i=2;i<=n;++i)
    {
        if (!p[i]) prime[++prime[0]]=i;
        range[i]=prime[0];
        for (int j=1;j<=prime[0]&&i*prime[j]<=n;++j)
        {
            p[i*prime[j]]=1;
            if (i%prime[j]==0) break;
        }
    }
}
LL fast_pow(LL a,int p)
{
    LL ans=1LL;
    for (;p;p>>=1,a=a*a%Mod)
        if (p&1)
            ans=ans*a%Mod;
    return ans;
}
void init()
{
    phi[0]=1LL;
    for (int i=1;i<=prime[0];++i)
    {
        LL now=(LL)(prime[i]-1)*fast_pow(prime[i]%Mod,Mod-2)%Mod;
        phi[i]=phi[i-1]*now%Mod;
    }
    mul[0]=1LL;
    for (int i=1;i<=maxn;++i) mul[i]=mul[i-1]*i%Mod;
}
int main()
{
    scanf("%d%lld",&T,&Mod);
    for (int i=1;i<=T;++i)
    {
        scanf("%d%d",&n[i],&m[i]);
        maxn=max(maxn,n[i]);
        maxm=max(maxm,m[i]);
    }
    get(maxm);
    init();
    for (int i=1;i<=T;++i)
    {
        ans=phi[range[m[i]]]*mul[n[i]]%Mod;
        printf("%lld\n",ans);
    }
}