题目链接
https://www.luogu.com.cn/problem/P1447
题解
为了方便起见，不妨设 \(n \leq m\)。
容易发现我们要求的是：
$$ans=\sum_{i=1}^n \sum_{j=1}^m (2 \times \gcd(i,j)-1)$$
我们先提出公因式：
$$ans=2 \sum_{i=1}^n \sum_{j=1}^m \gcd(i,j) – n \times m$$
到这里我们有两种做法。
做法一
（这个做法和 [POI2007]ZAP-Queries 一致）
套路性地枚举 \(\gcd\) 的值：
$$ans=2\sum_{d=1}^{n} d\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=d] -n \times m$$
我们设：
$$f(d)=\sum_{i=1}^{n} \sum_{j=1}^{m}[\gcd(i,j)=d]$$
要求的答案就变成了：
$$ans=2\sum_{d=1}^{n}d \times f(d) – n \times m$$
将 \(f(d)\) 套路性的除一个 \(d\)：
$$f(d)=\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}[\gcd(i,j)=1]$$
利用莫比乌斯函数的性质：\(\sum_{d|n}\mu(d)=[x=1]\) 将 \([\gcd(i,j)=1]\) 换掉：
$$f(d)=\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor} \sum_{x|\gcd(i,j)}\mu(x)$$
有这样一个性质：若 \(x|\gcd(i,j)\)，则 \(x|i\) 且 \(x|j\)。所以我们把这个条件拆开：
$$f(d)=\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor} \sum_{x|i,x|j}\mu(x)$$
接下来枚举 \(x\)：
$$f(d)=\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor} \sum_{x=1}^{a}\mu(x)[x|i][x|j]$$
交换求和顺序：
$$f(d)=\sum_{x=1}^n \mu(x) \sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor} [x|i] \sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}[x|j]$$
从而得到：
$$f(d)=\sum_{k=1}^{n}\mu(k)\left \lfloor \frac{n}{kd} \right \rfloor\left \lfloor \frac{m}{kd} \right \rfloor$$
将 \(f(d)\) 代入 \(ans\) 中：
$$ans=2\sum_{i=1}^n d \sum_{k=1}^{n}\mu(k)\left \lfloor \frac{n}{kd} \right \rfloor\left \lfloor \frac{m}{kd} \right \rfloor – n \times m$$
对于每个 \(d\)，我们都需要整除分块一次，时间复杂度 \(O(n \ln n)\)。
做法二
还能再快一点吗？
欧拉函数有这样一个性质：\(\sum_{d|n}\varphi(d)=n\)。
于是我们把刚开始的 \(\gcd(i,j)\) 换掉：
$$ans=2 \sum_{i=1}^n \sum_{j=1}^m \sum_{d|\gcd(i,j)}\varphi(d) – n \times m$$
把内层的条件拆开：
$$ans=2 \sum_{i=1}^n \sum_{j=1}^m \sum_{d|i,d|j}\varphi(d) – n \times m$$
交换求和顺序：
$$ans=2\sum_{d=1}^n \varphi(d) \sum_{i=1}^n [d|i] \sum_{j=1}^m [d|j] – n \times m$$
从而得到：
$$ans=2\sum_{d=1}^n \varphi(d)\left \lfloor \frac{n}{d} \right \rfloor \left \lfloor \frac{m}{d} \right \rfloor – n \times m$$
只需一次 \(O(n)\) 的线性筛和一次 \(O(\sqrt n)\) 的整除分块就解决本题了。
（多组询问的时候就吊打做法一了）
#include <iostream>
#include <algorithm>
#define N 100000
using namespace std;
long long pri[100005],phi[100005];
void init()
{
phi[1]=1;
int cnt=0;
for(int i=2;i<=N;i++)
{
if(!phi[i])
{
phi[i]=i-1;
pri[++cnt]=i;
}
for(long long j=1;j<=cnt&&i*pri[j]<=N;j++)
{
if(i%pri[j]==0)
{
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
phi[i*pri[j]]=phi[i]*phi[pri[j]];
}
}
for(int i=1;i<=N;i++)
phi[i]+=phi[i-1];
}
int main()
{
long long n,m;
cin>>n>>m;
init();
long long ans=0;
if(n>m)swap(n,m);
for(int l=1,r;l<=n;l=r+1)
{
r=min(n/(n/l),m/(m/l));
ans+=(phi[r]-phi[l-1])*(n/l)*(m/l);
}
ans=ans*2-n*m;
cout<<ans<<endl;
return 0;
}