题目描述

  计算：

\[\sum_{i=1}^{n}\sum_{j=1}^{m}\Big(2\times\gcd(i,j)-1\Big) \]

  数据范围：\(1\leq n,m\leq 10^5\)。

分析

\[\begin{aligned}&\sum_{i=1}^{n}\sum_{j=1}^{m}\Big(2\times\gcd(i,j)-1\Big)\\=&2\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)-n\times m\end{aligned} \]

  设 \(f(k)=\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k]\)（假设 \(n\leq m\)）。

\[\begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=d]\\=&\sum_{i=1}^{\frac{n}{k}}\sum_{j=1}^{\frac{m}{k}}[\gcd(i,j)=1]\\=&\sum_{i=1}^{\frac{n}{k}}\sum_{j=1}^{\frac{m}{k}}\sum_{d\mid \gcd(i,j)}\mu(d)\\=&\sum_{i=1}^{\frac{n}{k}}\sum_{j=1}^{\frac{m}{k}}\sum_{d=1}^{\frac{n}{k}}\mu(d)·[d\mid \gcd(i,j)]\\=&\sum_{d=1}^{\frac{n}{k}}\mu(d)\sum_{i=1}^{\frac{n}{k}}\sum_{j=1}^{\frac{m}{k}}[d\mid \gcd(i,j)]\\=&\sum_{d=1}^{\frac{n}{k}}\mu(d)\Big\lfloor\frac{n}{kd}\Big\rfloor\Big\lfloor\frac{m}{kd}\Big\rfloor\end{aligned} \]

  利用数论分块：

\[\begin{aligned}&\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)\\=&\sum_{k=1}^{n}f(k)\times k\\=&\sum_{k=1}^{n}k\sum_{d=1}^{\frac{n}{k}}\mu(d)\Big\lfloor\frac{n}{kd}\Big\rfloor\Big\lfloor\frac{m}{kd}\Big\rfloor\\=&\sum_{k=1}^{n}k\sum_{kd=1}^{n}\mu(d)\Big\lfloor\frac{n}{kd}\Big\rfloor\Big\lfloor\frac{m}{kd}\Big\rfloor\end{aligned} \]

  设 \(x=kd\)：

\[\begin{aligned}=&\sum_{k=1}^{n}k\sum_{x=1}^{n}[k\mid x]\mu(\frac{x}{k})\Big\lfloor\frac{n}{x}\Big\rfloor\Big\lfloor\frac{m}{x}\Big\rfloor\\=&\sum_{k=1}^{n}\sum_{k\mid x}^{n}k\mu(\frac{x}{k})\Big\lfloor\frac{n}{x}\Big\rfloor\Big\lfloor\frac{m}{x}\Big\rfloor\end{aligned} \]

  改变 \(k,x\) 的枚举顺序（即先枚举 \(x\)，再枚举 \(k\)），所以把第一个求和中的 \(k\) 替换成 \(x\)，结果不会产生变化：

\[\begin{aligned}=&\sum_{x=1}^{n}\sum_{k\mid x}^{n}k\mu(\frac{x}{k})\Big\lfloor\frac{n}{x}\Big\rfloor\Big\lfloor\frac{m}{x}\Big\rfloor\\=&\sum_{x=1}^{n}\Big\lfloor\frac{n}{x}\Big\rfloor\Big\lfloor\frac{m}{x}\Big\rfloor\sum_{k\mid x}^{n}k\mu(\frac{x}{k})\end{aligned} \]

  可以发现右边的求和式为 \(\mathbf{id}\ast \mu=\varphi\)，所以：

\[=\sum_{x=1}^{n}\Big\lfloor\frac{n}{x}\Big\rfloor\Big\lfloor\frac{m}{x}\Big\rfloor\varphi(x) \]

  预处理欧拉函数前缀和，然后数论分块，时间复杂度 \(O(n+\sqrt{n})\)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
long long n,m;
long long sum[N+10];
bool vis[N+10];
long long prime[N+10],phi[N+10],cnt;
void init()
{
    phi[1]=1;
    for(int i=2;i<=N;i++)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    for(int i=1;i<=N;i++)
        sum[i]=sum[i-1]+phi[i];
}
int main()
{
    init();
    cin>>n>>m;
    if(n>m)
        swap(n,m);
    long long ans=0;
    for(long long l=1,r;l<=n;l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        ans=ans+1ll*(sum[r]-sum[l-1])*(n/l)*(m/l);
    }
    ans=2*ans-n*m;
    cout<<ans<<endl;
    return 0;
}