P1390 公约数的和（莫比乌斯反演）

P1390 公约数的和

题意：

给定n，求
$$\sum _{i=1}^n\sum _{j=i+1}^{n}gcd(i,j)$$
其中gcd(i,j)表示i和j的最大公约数。

Solution：

法一：

$$\begin{gathered} \sum _{i=1}^n\sum _{j=i+1}^{n}gcd(i,j) \\ =\sum _{d=1}^{n}d\sum _{i=1}^n\sum _{j=i+1}^n[gcd(i,j)=d] \\ =\sum _{d=1}^{n}d\frac{{\sum }_{i=1}^n{\sum }_{j=1}^n[gcd(i,j)=d]-{\sum }_{i=1}^n{\sum }_{j=i}^i[gcd(i,j)=d]}{2} \\ =\sum _{d=1}^{n}d\frac{{\sum }_{i=1}^n{\sum }_{j=1}^n[gcd(\frac{i}{d},\frac{j}{d})=1]-{\sum }_{i=1}^n{\sum }_{j=i}^i[gcd(\frac{i}{d},\frac{j}{d})=1]}{2} \\ =\sum _{d=1}^{n}d\frac{{\sum }_{i=1}^{\frac{n}{d}}{\sum }_{j=1}^{\frac{n}{d}}[gcd(i,j)=1]-{\sum }_{i=1}^{\frac{n}{d}}{\sum }_{j=i}^i[gcd(i,j)=1]}{2} \\ =\sum _{d=1}^{n}d\frac{{\sum }_{i=1}^{\frac{n}{d}}{\sum }_{j=1}^{\frac{n}{d}}{\sum }_{k|gcd(i,j)}\mu (k)-{\sum }_{i=1}^{\frac{n}{d}}{\sum }_{j=i}^i{\sum }_{k|gcd(i,j)}\mu (k)}{2} \\ =\sum _{d=1}^{n}d\sum _{k=1}^{\frac{n}{d}}\mu (k)\frac{\lfloor \frac{n}{kd}{\rfloor }^2-\lfloor \frac{n}{kd}\rfloor }{2} \end{gathered}$$

法二：

假设$f(d)={\sum }_{i=1}^n{\sum }_{j=i+1}^n[gcd(i,j)=d]$
那么根据$F(n)={\sum }_{n|d}f(d)$
$$\begin{gathered} F(k)=\sum _{k|d}f(d) \\ =\sum _{k|d}\sum _{i=1}^n\sum _{j=i+1}^n[gcd(i,j)=d] \\ =\sum _{i=1}^n\sum _{j=i+1}^n[k|gcd(i,j)] \\ =\sum _{i=1}^n\sum _{j=1}^n[k|gcd(i,j)]-\sum _{i=1}^n\sum _{j=i}^i[k|gcd(i,j)] \\ =\frac{\lfloor \frac{n}{k}{\rfloor }^2-\lfloor \frac{n}{k}\rfloor }{2} \end{gathered}$$
之后根据$f(d)={\sum }_{d|k}\mu (\frac{k}{d})F(k)$
$$\begin{gathered} f(d)=\sum _{d|k}\mu (\frac{k}{d})F(k) \\ =\sum _{d|k}\mu (\frac{k}{d})\frac{\lfloor \frac{n}{k}{\rfloor }^2-\lfloor \frac{n}{k}\rfloor }{2} \end{gathered}$$
令k=td
$$\begin{gathered} \sum _{i=1}^n\sum _{j=i+1}^{n}gcd(i,j) \\ =\sum _{d=1}^{n}d\sum _{i=1}^n\sum _{j=i+1}^n[gcd(i,j)=d] \\ =\sum _{d=1}^{n}d\sum _{d|k}\mu (\frac{k}{d})\frac{\lfloor \frac{n}{k}{\rfloor }^2-\lfloor \frac{n}{k}\rfloor }{2} \\ =\sum _{d=1}^{n}d\sum _{t=1}^{\frac{n}{d}}\mu (t)\frac{\lfloor \frac{n}{td}{\rfloor }^2-\lfloor \frac{n}{td}\rfloor }{2} \end{gathered}$$
最后套个数论分块就可以了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
const int N=2e6;
int mu[N+5],prime[N+5],notPrime[N+5],cnt=0;
int sum[N];
void initMu()
{
   
    mu[1]=1;
    for(int i=2;i<=N;i++)
    {
   
        if(!notPrime[i])
        {
   
            prime[cnt++]=i;
            mu[i]=-1;
        }
        for(int j=0;j<cnt&&1ll*i*prime[j]<=N;j++)
        {
   
            notPrime[i*prime[j]]=1;
            if(i%prime[j])mu[i*prime[j]]=-mu[i];
            else{
   mu[i*prime[j]]=0;break;}
        }
    }
    for(int i=1;i<=N;i++)sum[i]=sum[i-1]+mu[i];
}
int n;
ll res=0;
int main()
{
   
    initMu();
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
    {
   
        ll ans=0;
        int x=n/i;
        for(int l=1,r;l<=x;l=r+1)
        {
   
            r=x/(x/l);
            ans=ans+1ll*(x/l)*(x/l-1)/2*(sum[r]-sum[l-1]);
        }
        //cout<<i*ans<<endl;
        res+=1ll*i*ans;
    }
    printf("%lld",res);
    return 0;
}

Another Solution

对于${\sum }_{d=1}^{n}d{\sum }_{d|k}\mu (\frac{k}{d})\frac{\lfloor \frac{n}{k}{\rfloor }^2-\lfloor \frac{n}{k}\rfloor }{2}$，根据$id\ast \mu =\phi$
$$\begin{gathered} \sum _{d=1}^n\sum _{d|k}id(d)\ast \mu (\frac{k}{d})\frac{\lfloor \frac{n}{k}{\rfloor }^2-\lfloor \frac{n}{k}\rfloor }{2} \\ =\sum _{k=1}^n\sum _{d|k}id(d)\ast \mu (\frac{k}{d})\frac{\lfloor \frac{n}{k}{\rfloor }^2-\lfloor \frac{n}{k}\rfloor }{2} \\ =\sum _{k=1}^n\phi (k)\frac{\lfloor \frac{n}{k}{\rfloor }^2-\lfloor \frac{n}{k}\rfloor }{2} \end{gathered}$$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
const int N=2e6;
int phi[N+5],prime[N+5],notPrime[N+5],cnt=0;
ll sum[N];
void initMu()
{
   
    phi[1]=1;
    for(int i=2;i<=N;i++)
    {
   
        if(!notPrime[i])
        {
   
            prime[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<cnt&&1ll*i*prime[j]<=N;j++)
        {
   
            notPrime[i*prime[j]]=1;
            if(i%prime[j])phi[i*prime[j]]=phi[i]*(prime[j]-1);
            else{
   phi[i*prime[j]]=phi[i]*prime[j];break;}
        }
    }
    for(int i=1;i<=N;i++)sum[i]=sum[i-1]+phi[i];
}
int n;
ll res=0;
int main()
{
   
    initMu();
    scanf("%d",&n);
    for(int l=1,r;l<=n;l=r+1)
    {
   
        r=n/(n/l);
        res+=1ll*(n/l)*(n/l-1)/2*(sum[r]-sum[l-1]);
    }
    printf("%lld",res);
    return 0;
}