「SDOI2008沙拉公主的困惑」

题目

看着有点可怕

求

\[\sum_{i=1}^{n!}[(i,m!)=1]
\]

考虑一下\(m=n\)的时候的答案

非常显然就是\(\varphi(m!)\)

而如果\(n>m\)

非常显然\(m!|n!\)

可以把\(n!\)想象成一个大数轴，将这个大数轴分成\(\frac{n!}{m!}\)部分，每一部分都有\(m!\)个数

第一部分的贡献是\(\varphi(m!)\)非常显然

第二部分的每个数\(k\)和\(m!\)求\(gcd\)

我们更相减损

\[(k,m!)=(m!,k-m!)
\]

\(k-m!\)对应了第一部分里的数，所以第二个块的贡献也是\(\varphi(m!)\)

剩下的每一个块都可以通过更相减损转化成上一个块，所以每一个快的答案都是\(\varphi(m!)\)

一共\(\frac{n!}{m!}\)个块，所以答案就是

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

通过分解质因数的方法去求\(\varphi(m!)\)非常不科学

我们考虑线性推出所有的\(\varphi(i!)\)

如果\(i\)为质数，那么\(i\)这个质因子在之前没有出现过，那么贡献是\(i-1\)

否则这些质因子在之前都出现过，所以贡献是\(i\)

代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#define re register

#define maxn 10000005

#define LL long long

#define inf 999999999

inline int max(int a,int b) {return a>b?a:b;}

inline int read()

{

    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

LL mod,phi[maxn];

int T,D,U;

struct Ask{int N,M,rk;}a[10005];

LL ans[100005];

inline int cmp(Ask A,Ask B) {return A.M<B.M;}

void exgcd(LL a,LL b,LL &x,LL &y) {if(!b) {x=1,y=0;return;}exgcd(b,a%b,y,x);y-=a/b*x;}

inline LL inv(LL a) {LL x,y;exgcd(a,mod,x,y);return (x%mod+mod)%mod;}

int f[maxn],p[maxn>>1];

int b[maxn];

LL fac[maxn];

int main()

{

    T=read();mod=read();

    for(re int i=1;i<=T;i++) a[i].N=read(),a[i].M=read(),a[i].rk=i,D=max(D,a[i].N),U=max(U,a[i].M);

    fac[0]=1;f[1]=1,phi[1]=1;

    for(re int i=2;i<=U;i++)

    {

        if(!f[i]) p[++p[0]]=i,phi[i]=(phi[i-1]*(LL)(i-1))%mod;

        	else phi[i]=(phi[i-1]*(LL)i)%mod;

        for(re int j=1;j<=p[0]&&p[j]*i<=U;j++)

        {

            f[p[j]*i]=1;

            if(i%p[j]==0) break;

        }

    }

    for(re int i=1;i<=D;i++) fac[i]=fac[i-1]*i%mod;

    for(re int i=1;i<=T;i++) printf("%lld\n",fac[a[i].N]*inv(fac[a[i].M])%mod*phi[a[i].M]%mod);

    return 0;

}

巴特西

「SDOI2008沙拉公主的困惑」

最新文章

热门文章