[莫比乌斯函数+线性筛求积性函数]BZOJ4804【欧拉心算】题解

题目概述

求 $\sum_{i=1}^{n}\sum_{j=1}^{n}\varphi(gcd(i,j))$ 。

解题报告

推式子:$\sum_{T=1}^{n}\lfloor{n\over T}\rfloor^2\sum_{d|T}\mu(d)\varphi({n\over d})$ 。

调和级数TLE,所以要想办法线性筛求出后面那个积性函数。

翰爷表示可以这样:记 $H(i)=\sum_{d|i}\mu(d)\varphi({i\over d})$ ,求出 $H(p^a)$ 和 $pw_i$ 表示 $i$ 最小质因子的幂对应的数,然后就可以直接这么求 $H(i)=H({i\over pw_i})H(pw_i)$ 。那么 $H(p^a)$ 分类讨论一下:

$$ H(p^a)= \begin{cases} p-2&a=1\\ (p-1)(p^a-p^{a-1})&a>1 \end{cases} $$

这样常数稍大但是很无脑啊,感觉挺资瓷的。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=10000000;

int te,n,p[maxn+5],pw[maxn+5];bool pri[maxn+5];LL H[maxn+5],ans;

inline void Make(){
    pri[0]=pri[1]=true;H[1]=1;
    for (int i=2;i<=maxn;i++){
        if (!pri[i]) p[++p[0]]=i,pw[i]=i,H[i]=i-2;
        for (int j=1,t;j<=p[0]&&(t=(i*p[j]))<=maxn;j++)
            if (!(i%p[j])){pw[t]=pw[i]*p[j];
                if (t==pw[t]) H[t]=(LL)(p[j]-1)*(i-i/p[j]);
                else H[t]=H[t/pw[t]]*H[pw[t]];pri[t]=true;break;
            } else pw[t]=p[j],H[t]=H[i]*H[p[j]],pri[t]=true;
    }for (int i=1;i<=maxn;i++) H[i]+=H[i-1];
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (Make(),scanf("%d",&te);te;printf("%lld\n",ans),te--){scanf("%d",&n);ans=0;
        for (int l=1,r;l<=n;l=r+1) r=n/(n/l),ans+=(H[r]-H[l-1])*(n/l)*(n/l);
    }return 0;
}

本文链接:https://zigzagk.top/2018/09/09/BZOJ4804
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 CN 许可协议。转载请注明作者和出处QwQ。