容斥思想的一道好题。
题目容易转化为：
\[2\times \sum_{i=1}^n \sum_{j=1}^n (\gcd(i, j))\ - nm. \]直接求和不好求，不妨转换为枚举 \(d=\gcd(i,j)\)。
那么 \(i,j\) 应该均为 \(d\) 的倍数。记 \(f(i)=\left \lfloor \frac{n}{i} \right \rfloor \cdot \left \lfloor \frac{m}{i} \right \rfloor\)，但发现会有虽然都是 \(i\) 的倍数，但 \(\gcd\) 并不是 \(i\) 的数，考虑如何去除。
记 \(g(i)\) 为 \(\gcd(x,y)=i\) 的数量，容易发现 \(f(i)={\textstyle \sum \limits_{j=1}^{\left \lfloor \frac{n}{i} \right \rfloor} g(i\cdot j)}\)。
\(f(i)\) 是好求的，我们倒着处理 \(g(i)\)。复杂度是调和级数 \(\mathcal O(n\log n)\)。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll MOD=1e9+7;
// head
const int N=1e5+5;
int f[N],g[N];
signed main()
{
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n,m;cin>>n>>m;
int nn=min(n,m);
for(int i=1;i<=nn;i++) f[i]=(n/i)*(m/i);
for(int i=nn;i>=1;i--){
int cnt=0;
for(int j=i*2;j<=nn;j+=i){
cnt+=g[j];
}
g[i]=f[i]-cnt;
}
int ans=0;
for(int i=1;i<=nn;i++) ans+=g[i]*i;
cout<<2*ans-m*n<<endl;
}