解法

这道题是一道裸题，考察莫比乌斯反演和 Dirichlet 卷积的知识。

在这里我们规定\(n<m\)，这两者调换不会对答案产生影响。然后我们来观察这个计数规律，发现每一个点对答案的贡献至少为\(1\)，附加的贡献其实就是当前线段上除了本身的整点（整数坐标点）个数的两倍，换句话说就是：

\[ ans = \sum_{i = 1}^n \sum_{j = 1}^m 1 + 2( gcd(i, j) – 1 ) \]

化简一下就是：

\[ ans = 2 \left( \sum_{i = 1}^n \sum_{j = 1}^m gcd(i, j) \right) – nm \]

我们可以把重点放在\( \left( \sum_{i = 1}^n \sum_{j = 1}^m gcd(i, j) \right) \)上，可以考虑直接枚举\(gcd(i, j) = d\)然后加一个条件表达式：

\[ \sum_{d = 1}^n \sum_{i = 1}^n \sum_{j = 1}^m d [gcd(i, j) = d] \]

考虑提出一个\(d\)，并且在后面的两个和式中除掉一个\(d\)：

\[ \sum_{d = 1}^n d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} [gcd(i, j) = 1] \]

看到经典的\(\epsilon\)函数就立马想到莫比乌斯反演（\(\mu * I = \epsilon\)），考虑带入：

\[ \sum_{d = 1}^n d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} \sum_{h|i, h|j} \mu(h) \]

考虑把\( \sum_{h|i, h|j} \mu(h) \)中间的条件写成判别表达式\( [h|i][h|j] \)，并把\(h\)的枚举提到前面去：

\[ \sum_{d = 1}^n d \sum_{h = 1}^{\lfloor \frac{n}{d} \rfloor} \mu(h) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} [h|i][h|j] \]

发现可以直接除掉\(h\)来化简：

\[ \sum_{d = 1}^n d \sum_{h = 1}^{\lfloor \frac{n}{hd} \rfloor} \mu(h) \sum_{i = 1}^{\lfloor \frac{n}{hd} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{hd} \rfloor} 1 \\ \sum_{d = 1}^n d \sum_{h = 1}^{\lfloor \frac{n}{hd} \rfloor} \mu(h) \lfloor \frac{n}{hd} \rfloor \lfloor \frac{m}{hd} \rfloor \]

考虑枚举\(T = hd\)，注意条件的问题：

\[ \sum_{d = 1}^n d \sum_{d|T}^n \mu(\lfloor \frac{T}{d} \rfloor) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \]

考虑调换求和顺序，交换\(T\)和\(d\)的枚举：

\[ \sum_{T = 1}^n \sum_{d|T} d \mu(\lfloor \frac{T}{d} \rfloor) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \]

提取之后发现神奇性质：

\[ \sum_{T = 1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{d|T} d \mu(\frac{T}{d}) \]

这不卷积么：\( \sum_{d|T} d \mu(\frac{T}{d}) \)，回忆起有\(id * \mu = \varphi\)（不记得的话这里有证明），果断带入\(\varphi\)：

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

整除分块之后这道题就搞定了。

代码

// P1447.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int MAX_N = 101000;

ll phi[MAX_N], prime[MAX_N], n, m, tot;
bool vis[MAX_N];

int main()
{
    scanf("%lld%lld", &n, &m);
    if (n > m)
        swap(n, m);
    phi[1] = 1;
    for (int i = 2; i < MAX_N; i++)
    {
        if (!vis[i])
            phi[prime[++tot] = i] = i - 1;
        for (int j = 1; j <= tot && i * prime[j] < MAX_N; j++)
        {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
    for (int i = 1; i < MAX_N; i++)
        phi[i] += phi[i - 1];
    ll ans = 0;
    for (ll T = 1, gx; T <= n; T = gx + 1)
    {
        gx = min(n / (n / T), m / (m / T));
        ans += (phi[gx] - phi[T - 1]) * (n / T) * (m / T);
    }
    ans = 2 * ans - n * m;
    printf("%lld", ans);
    return 0;
}