题解 P1390 【公约数的和】

· · 题解

总结一下这类问题的两种解法：

完全就是套路嘛...... $$\sum_{i=1}^n\sum_{j=1}^{i-1}gcd(i,j)$$ $$=\frac{\sum\limits_{i=1}^n\sum\limits_{j=1}^ngcd(i,j)-\sum\limits_{i=1}^ngcd(i,i)}{2}$$ 只看分子前半部分（其它的都是$O(1)$处理）： $$\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)$$ $$=\sum_{k=1}^nk\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=k]$$ $$=\sum_{k=1}^nk\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{d|gcd(i,j)}\mu(d)$$ $$=\sum_{k=1}^nk\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor}[gcd(i,j)=1]$$ $$=\sum_{k=1}^nk\sum_{d=1}^n\mu(d)\lfloor\frac{n}{kd}\rfloor^2$$ 令$T=kd =\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor^2\sum_{k|T}k\mu(\frac{T}{k}) =\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor^2\varphi(T) 时间复杂度：预处理$O(n)$，查询$O(\sqrt n)$（不分块的话是$O(n)$） $(2)$ 直接推倒+线性筛$\varphi \sum_{i=1}^n\sum_{j=1}^{i-1}gcd(i,j) =\sum_{i=1}^n\sum_{k|i}k\sum_{j=1}^{i-1}[gcd(i,j)=k] =\sum_{i=1}^n\sum_{k|i}k\sum_{j=1}^{\frac{i}{k}-1}[gcd(\frac{i}{k},j)=1] =\sum_{i=1}^n\sum_{k|i}k\varphi(\frac{i}{k}) 说明： $(1)$ 解法$1$最后输出需要加上省略掉的部分（其实就是减去$\frac{n(n+1)}{2}$后再除以$2$） $(2)$ 解法$2$中的$\varphi(1)$需要特殊地定义为$0$（看看式子就知道为什么了） $(3)$ **一定要开long long！！！！！** 时间复杂度：预处理$O(\sum_{i=1}^n\sum_{d|n}1)$（即$1$~$n$中所有数的约数个数和），查询$O(1)

显然，解法2更适用于询问组数特别多的时候，在这道题里并不是很优。

贴个图：

解法1：

解法2：

可见，此题中解法1吊打解法2

代码（2种解法）：

//解法1
#include <bits/stdc++.h>
using namespace std;
#define N 2000005
#define ll long long
int n,prm[N],phi[N];ll ans,sPhi[N];bool vs[N];
void sieve(int x)
{
    vs[1]=phi[1]=sPhi[1]=1;
    for(int i=2;i<=x;++i)
    {
        if(!vs[i]) prm[++prm[0]]=i,phi[i]=i-1;
        for(int j=1;i*prm[j]<=x;++j)
        {
            vs[i*prm[j]]=1;if(!(i%prm[j])) {phi[i*prm[j]]=phi[i]*prm[j];break;}
            phi[i*prm[j]]=phi[i]*(prm[j]-1);
        }
        sPhi[i]=sPhi[i-1]+phi[i];
    }
}
int main()
{
    scanf("%d",&n);sieve(n);
    for(int i=1,t;i<=n;i=t+1) t=n/(n/i),ans+=1ll*(sPhi[t]-sPhi[i-1])*(n/i)*(n/i);
    printf("%lld\n",ans-(1ll*n*(n+1)>>1)>>1);
}
//解法2
#include <bits/stdc++.h>
using namespace std;
#define N 2000005
#define ll long long
int n,prm[N],phi[N];ll ans,f[N],g[N];bool vs[N];
void sieve(int x)
{
    vs[1]=1;
    for(int i=2;i<=x;++i)
    {
        if(!vs[i]) prm[++prm[0]]=i,phi[i]=i-1;
        for(int j=1;i*prm[j]<=x;++j)
        {
            vs[i*prm[j]]=1;if(!(i%prm[j])) {phi[i*prm[j]]=phi[i]*prm[j];break;}
            phi[i*prm[j]]=phi[i]*(prm[j]-1);
        }
    }
    for(int i=1;i*i<=x;++i)
    {f[i*i]+=i*phi[i];for(int j=i+1;i*j<=x;++j) f[i*j]+=i*phi[j]+j*phi[i];}
    for(int i=1;i<=x;++i) g[i]=g[i-1]+f[i];
}
int main() {scanf("%d",&n);sieve(n);printf("%lld\n",g[n]);}