由题意不难得到当点的坐标为$(x, y)$时,能量损失为$2×(gcd(x, y) - 1) + 1$,考虑用$dp$求解出$gcd(x, y) = i$的点对数量
$dp[i]$:$gcd(x, y) = i$的点对数量$(1 \leq i \leq min(n, m))$
考虑如何计算$dp[i]$:首先计算出公因数为$i$的点对数量,不难得到此数量为$\lfloor {n\over i} \rfloor × \lfloor {m\over i} \rfloor$(即$[1, n]$中$i$的倍数数量乘上$[1, m]$中$i$的倍数数量),接着考虑容斥,公因数为$i$的两个数的$gcd$一定是$i$的倍数,但不一定恰好就是$i$,所以需要减去公因数为$i$但是$gcd$是$(2i、3i、…ki)$的点对数量,即减去$\sum_{k = 2}dp[k * i]$,其中满足$k * i \leq min(n, m)$
由调和级数不难得到时间复杂度为$O(min(n, m)log(min(n, m)))$
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve()
{
int n, m;
cin >> n >> m;
int k = min(n, m);
vector<LL> dp(k + 1);
for (int i = k; i; i -- )
{
dp[i] = 1ll * (n / i) * (m / i);
for (int j = 2 * i; j <= k; j += i)
dp[i] -= dp[j];
}
LL res = 0;
for (int i = 1; i <= k; i ++ )
res += 1ll * dp[i] * (2 * i - 1);
cout << res << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T -- ) solve();
return 0;
}