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;
}