Cptraser/ 十月 30, 2018/ 2018.10/ 0 comments

[SDOI2008]沙拉公主的困惑

题面传送门

上PoPoQQQ大爷的题解

若一个数xm!互质,那么x+(m!)也一定与m!互质,(x+m! * 2)也一定与m!互质.
由于n!一定是m!的倍数,于是我们每存在到一个x<=m!m!互质,我们就一定能找到(n!)/(m!)个与m!互质的数
m!以内与m!互质的数的数量恰好是\varphi(m!)

所以答案等于:

    \[\frac{\varphi(m!) * (n!)}{m!} \% p\]

考虑\varphi(m!)的展开式:

    \[\varphi(m!)=m!\prod(1-\frac{1}{p_i})\]

Tips m!的质因数恰好是m以内的质数。
答案变成:

    \[n!\prod(1-\frac{1}{p_i})\% p\]

两个都线性可筛。

#include <bits/stdc++.h>
using namespace std;

int read(){
    char c;while(c=getchar(),c<'0'||c>'9');
    int x=c-'0';while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0';
    return x;
}

const int Maxn=1e7+5;
int T,Mod,Inv[Maxn],Fac[Maxn],Prime[Maxn],Vis[Maxn],Cnt;
int G[Maxn];

void Gp(void){
    for(int i=2;i<=Maxn-5;i++){
        if(!Vis[i])Prime[++Cnt]=i;
            for(int j=1;j<=Cnt;j++){
                if(Prime[j]*i>Maxn-5)break;
                Vis[Prime[j]*i]=1;
                if(!(i%Prime[j]))break;
            }
    }
}

void Gl(void){
    int Now=1,i;
    G[1]=1;for(i=2;i<=Maxn-5;i++){
        if(i==Prime[Now])
            G[i]=1ll*G[i-1]*(Prime[Now]-1)%Mod*Inv[Prime[Now]]%Mod,(G[i]+=Mod)%=Mod,Now++;
        else G[i]=G[i-1];
    }
}

int main()
{
    int i;
    T=read(),Mod=read(),Inv[1]=Fac[1]=Fac[0]=1,Gp();
        for(i=2;i<=Maxn-5;i++)
            Inv[i]=1ll*(Mod-(Mod/i))*Inv[Mod%i]%Mod;
        for(i=2;i<=Maxn-5;i++)Fac[i]=1ll*Fac[i-1]*i%Mod;Gl();
        for(;T;T--){
            int N=read(),M=read();
            printf("%d\n",(1ll*Fac[N]*G[M]%Mod+Mod)%Mod);
        }
    return 0;
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*