题解 P6788 【「EZEC-3」四月樱花】

· · 题解

P6788 「EZEC-3」四月樱花解题报告：

更好的阅读体验

这是一道比较套路的推柿子题，代码短，可惜我不会做

题意

求

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

对一质数p取模，其中d(x)为x的约数个数。

数据范围：1\leqslant t\leqslant 2.5\cdot 10^9,1\leqslant p\leqslant 1.1\cdot 10^9

分析

考场上看到y^{d(y)}就想到\prod_{w\mid y}y去了，结果死活想不出来用w\cdot\frac{y}{w}来替代y，最后写了个O(t\log t)的暴力丢人/kk。

可能是求和做多了，一看到求积就蒙了

首先我们有：

\prod_{d\mid x} d^2=\prod_{d\mid x}(d\cdot\frac{x}{d})=\prod_{d\mid x}y=y^{d(y)}

所以原式可以转换一下：

\prod_{x=1}^t\prod_{y\mid x}\frac{y^{d(y)}}{\prod_{z\mid y}(z+1)^2}=\prod_{x=1}^t\prod_{y\mid x}\frac{\prod_{w\mid y} w^2}{\prod_{z\mid y}(z+1)^2}\\=\prod_{x=1}^t\prod_{y\mid x}\prod_{z\mid y}\frac{z^2}{(z+1)^2}\\=(\prod_{x=1}^t\prod_{y\mid x}\prod_{z\mid y}\frac{z}{z+1})^2

然后比较套路地枚举z，这样式子可以转化为：

(\prod_{z=1}^t\prod_{z\mid y}^t\prod_{y\mid x}^t\frac{z}{z+1})^2

套路枚举倍数，然后把求积转化为指数上的求和：

\prod_{x=1}^t\prod_{y\mid x}\frac{y^{d(y)}}{\prod_{z\mid y}(z+1)^2}=(\prod_{z=1}^t\prod_{y=1}^{\lfloor\frac{t}{z}\rfloor}\prod_{x=1}^{\lfloor\frac{t}{z\cdot y}\rfloor}\frac{z}{z+1})^2\\=(\prod_{z=1}^t(\frac{z}{z+1})^{\sum_{y=1}^{\lfloor\frac{t}{z}\rfloor}\sum_{x=1}^{\lfloor\frac{t}{z\cdot y}\rfloor}1})^2

注意一下，这里有一个细节，第二个式子的第三个\prod中：\prod_{x=1}^{\lfloor\frac{t}{z\cdot y}\rfloor}，之所以上面是\lfloor\frac{t}{z\cdot y}\rfloor而不是\lfloor\frac{t}{y}\rfloor，是因为这里y是枚举z的倍数，此时y代表的数应该为z\cdot y。

展开\sum，就会有：

\prod_{x=1}^t\prod_{y\mid x}\frac{y^{d(y)}}{\prod_{z\mid y}(z+1)^2}=(\prod_{z=1}^t(\frac{z}{z+1})^{\sum_{y=1}^{\lfloor\frac{t}{z}\rfloor}\lfloor\frac{t}{z\cdot y}\rfloor})^2

因为\lfloor\frac{a}{b\cdot c}\rfloor，所以上面\frac{z}{z+1}的指数可以看做\sum_{y=1}^{n}\lfloor\frac{n}{y}\rfloor，其中n=\lfloor\frac{t}{z}\rfloor，这样我们的指数就可以整除分块做到根号的复杂度了。

对\frac{z}{z+1}求积其实也是一样的，因为它们的指数满足整除分块的性质，所以可以对t进行整除分块。

但是还有一个小问题，如何求\prod_{i=l}^r\frac{i}{i+1}。我们只需要展开这个求积式，就有

\prod_{i=l}^r\frac{i}{i+1}=\frac{l}{l+1}\cdot\frac{l+1}{l+2}\cdots\frac{r}{r+1}

我们只需要抵消一下，答案就是\frac{l}{r+1}了。

代码

#include<stdio.h>
#define int long long
int i,j,k,m,n,mod,l,r,ans;
int ksm(int a,int b){
    b%=(mod-1);
    int res=1;
    while(b){
        if(b&1)
            res=res*a%mod;
        a=a*a%mod,b>>=1;
    }
    return res;
}
int calc(int n){
    int l=1,r,res=0;
    while(l<=n){
        r=n/(n/l);
        res+=(r-l+1)*(n/l);
        l=r+1;
    }
    return res;
}
signed main(){
    scanf("%lld%lld",&n,&mod);
    l=1,r=0,ans=1;
    while(l<=n){
        r=n/(n/l);
        ans=(ans*ksm(l*ksm(r+1,mod-2)%mod,calc(n/l))%mod)%mod;
        l=r+1;
    }
    printf("%lld\n",ans*ans%mod);
    return 0;
}

更新

然而现在出题人卡掉了上述的算法，现在对上面进行加速。

把上面的式子搬下来：

\prod_{x=1}^t\prod_{y\mid x}\frac{y^{d(y)}}{\prod_{z\mid y}(z+1)^2}=(\prod_{z=1}^t(\frac{z}{z+1})^{\sum_{y=1}^{\lfloor\frac{t}{z}\rfloor}\lfloor\frac{t}{z\cdot y}\rfloor})^2

上面的指数我们还可以化为：\sum_{y=1}^{\lfloor\frac{t}{x}\rfloor} d(y)，然后我们可以用一个神奇的科技来处理d的前缀和：杜教套杜教！

因为d=I\cdot I,I\cdot\mu=\epsilon，所以有d\cdot\mu=\epsilon

然后掏出杜教筛的式子·

g(1)\cdot S(n)=\sum_{i=1}^n(f\cdot g)(i)-\sum_{i=2}^n g(i)\cdot S(\lfloor\frac{n}{i}\rfloor)

带入进去：

\mu(1)\cdot Sumd(n)=\sum_{i=1}^n I(i)-\sum_{i=2}^n\mu(i)\cdot Sumd(\lfloor\frac{n}{i}\rfloor)=n-\sum_{i=2}^n\mu(i)\cdot Sumd(\lfloor\frac{n}{i}\rfloor)

我们需要对后面的式子进行整除分块，所以我们需要筛出\mu的前缀和，这里需要另一个杜教筛（

代码

#include<stdio.h>
#include<map>
#define int long long
using namespace std;
const int maxn=5000005;
int i,j,k,m,n,mod,ans,cnt;
int a[maxn],p[maxn],d[maxn],r[maxn],mu[maxn],sumd[maxn],summu[maxn];
map<int,int>ansd,ansmu;
int ksm(int a,int b){//快速幂
    b%=(mod-1);//用费马小定理处理一下
    int res=1;
    while(b){
        if(b&1)
            res=res*a%mod;
        a=a*a%mod,b>>=1;
    }
    return res;
}
int getmu(int n){//杜教筛筛出莫比乌斯函数
    if(n<maxn)
        return summu[n];
    if(ansmu.count(n))
        return ansmu[n];
    int l=2,r,res=1;
    while(l<=n){
        r=n/(n/l);
        res-=(r-l+1)*getmu(n/l);
        l=r+1;
    }
    return ansmu[n]=res;
}
int getd(int n){//杜教筛筛出约数函数
    if(n<maxn)
        return sumd[n];
    if(ansd.count(n))
        return ansd[n];
    int l=2,r,res=n;
    while(l<=n){
        r=n/(n/l);
        res-=(getmu(r)-getmu(l-1))*getd(n/l);
        l=r+1;
    }
    return ansd[n]=res;
}
void init(){//线性筛筛出2/3的前缀和
    p[1]=1,d[1]=1,r[1]=1,mu[1]=1;
    for(int i=2;i<maxn;i++){
        if(p[i]==0)
            a[++cnt]=i,d[i]=2,r[i]=1,mu[i]=-1;
        for(int j=1;j<=cnt;j++){
            if(i*a[j]>=maxn)
                break;
            p[i*a[j]]=1;
            if(i%a[j]==0){
                r[i*a[j]]=r[i]+1;
                d[i*a[j]]=d[i]/r[i*a[j]]*(r[i*a[j]]+1);
                mu[i*a[j]]=0;
                break;
            }
            r[i*a[j]]=1;
            d[i*a[j]]=d[i]*2;
            mu[i*a[j]]=-mu[i];
        }
    }
    for(int i=1;i<maxn;i++)
        sumd[i]=sumd[i-1]+d[i],summu[i]=summu[i-1]+mu[i];
}
int getans(int n){//对答案进行整除分块
    int l=1,r=0,res=1;
    while(l<=n){
        r=n/(n/l);
        res=(res*ksm(l*ksm(r+1,mod-2)%mod,getd(n/l))%mod)%mod;
        l=r+1;
    }
    return res;
}
signed main(){
    scanf("%lld%lld",&n,&mod);
    init();
    ans=getans(n);
    printf("%lld\n",ans*ans%mod);
    return 0;
}