LG P6788 「EZEC-3」四月樱花

Description

在樱花盛开的四月，Muxii 望着满天飘落的樱花，向身旁的 ZZH 问道：

“究竟有多少朵樱花在这个四月飘落？”

ZZH 答道：“樱花飘落的朵数 $s$与时间 $t$ 有如下关系：

$s=\prod_{x=1}^t \prod_{y|x} \frac{y^{d(y)}}{\prod_{z|y}(z+1)^2}$

其中 $d(y)$ 表示 $y$ 的约数个数。”

但作为一个文科生萌新，Muxii 显然无法清楚地知道具体的数目，因此他只好继续向 ZZH 询问这个问题的答案。

由于数量可能很大，所以你只需要替 ZZH 告诉 Muxii 他所需要的答案对 $p$ 取模的结果就好了。

Solution

题中所求为

$$ans=\left(\prod_{x=1}^n\prod_{y|x}\frac{y^{d(y)}}{\prod_{z|y}(z+1)^2}\right)\bmod p$$

大力操作式子：因为

$$y^{d(y)}=\prod_{z|y}y=\prod_{z|y}z\cdot\frac{y}{z}=\prod_{z|y}z^2$$

和

$$\sum_{z|y,y|n}=d(\frac{n}{z})$$

所以

$$s=\prod_{x=1}^n\prod_{y|x}\frac{y^{d(y)}}{\prod_{z|y}(z+1)^2}=\prod_{x=1}^n\prod_{y|x}\prod_{z|y}\left(\frac{z}{z+1}\right)^2=\prod_{z=1}^n\left(\frac{z}{z+1}\right)^{2sumd(\lfloor\frac{n}{z}\rfloor)}$$

其中$sumd(n)=\sum_{i=1}^n d(i)$

由于要求$d$的前缀和，所以有杜教筛

设$f=d=1*1，g=\mu$，则$f*g=1*1*\mu=1$，可以使用杜教筛，现在需要求出$\mu$的前缀和

再次使用杜教筛即可

求原式的值可以用整除分块做

时间复杂度$\Theta(n^{\frac 23}+\sqrt{n}\log n)$

#include<iostream>

#include<cstdio>

using namespace std;

long long n,mod,pmod,prime[],mu[],minn[],d[],tot,summu[],sumd[],ans=;

bool isprime[],vst[];

inline long long read()

{

    long long w=,f=;

    char ch=;

    while(ch<''||ch>'')

    {

        if(ch=='-')

            f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        w=(w<<)+(w<<)+ch-'';

        ch=getchar();

    }

    return w*f;

}

long long Mu(long long x)

{

    return x<=?mu[x]:summu[n/x];

}

long long D(long long x)

{

    return x<=?d[x]:sumd[n/x];

}

void djs(long long N)

{

    if(N<=||vst[n/N])

    {

        return;

    }

    vst[n/N]=true;

    for(long long l=;l<=N;)

    {

        long long r=N/(N/l);

        djs(N/l);

        (summu[n/N]+=(pmod-(r-l+)*Mu(N/l)%pmod)%pmod)%=pmod;

        l=r+;

    }

    (summu[n/N]+=)%=pmod;

    for(long long l=;l<=N;)

    {

        long long r=N/(N/l);

        (sumd[n/N]+=pmod-((Mu(r)-Mu(l-)+pmod)%pmod)*D(N/l)%pmod)%=pmod;

        l=r+;

    }

    (sumd[n/N]+=N)%=pmod;

}

long long ksm(long long a,long long p)

{

    long long ret=;

    while(p)

    {

        if(p&)

        {

            (ret*=a)%=mod;

        }

        (a*=a)%=mod;

        p>>=;

    }

    return ret;

}

int main()

{

    n=read();

    mod=read();

    pmod=mod-;

    mu[]=d[]=;

    for(long long i=;i<=;i++)

    {

        if(!isprime[i])

        {

            prime[++tot]=i;

            mu[i]=-;

            d[i]=;

            minn[i]=;

        }

        for(long long j=;j<=tot&&i*prime[j]<=;j++)

        {

            isprime[i*prime[j]]=true;

            if(!(i%prime[j]))

            {

                minn[i*prime[j]]=minn[i]+;

                d[i*prime[j]]=d[i]/(minn[i]+)*(minn[i*prime[j]]+);

                mu[i*prime[j]]=;

                break;

            }

            minn[i*prime[j]]=;

            d[i*prime[j]]=d[i]*d[prime[j]];

            mu[i*prime[j]]=mu[i]*-;

        }

    }

    for(long long i=;i<=;i++)

    {

        (d[i]+=d[i-])%=pmod;

        ((mu[i]+=mu[i-])+=pmod)%=pmod;

    }

    djs(n);

    for(long long l=;l<=n;)

    {

        long long r=n/(n/l);

        (ans*=ksm(l*ksm(r+,mod-)%mod,D(n/l)))%=mod;

        l=r+;

    }

    (ans*=ans)%=mod;

    printf("%lld\n",ans);

    return ;

}

四月樱花

巴特西

LG P6788 「EZEC-3」四月樱花

Description

Solution

最新文章

热门文章