算法

(数论、容斥原理) $O(R\log R)$

• 我们先不考虑 $x \neq g$ 且 $y \neq g$ 而只关心 $g \neq 1$

问题：对于任意 $k \in \{2, 3, \cdots, R\}$，统计 $L \leqslant x, y \leqslant R$ 使得 $\gcd(x, y) = k$ 的元素对个数。

记 $f(k)$ 为 $\gcd(x, y) = k$ 的元素对数量，$f’(k)$ 为 $\gcd(x, y)$ 是 $k$ 的倍数的元素对数量

只需求 $\displaystyle \sum_{k = 2}^R f(k)$ 即可。

$f’(k) = (\lfloor \frac{R}{k} \rfloor - \lfloor \frac{L - 1}{k} \rfloor)^2$
$f(k) = f’(k) - f(2k) - f(3k) - \cdots$

• 考虑 $x \neq g$ 且 $y \neq g$：

为了计算方便，我们可以先处理它的对立事件，也就是 $x = g$ 或 $y = g$：
由于 $x$ 和 $y$ 都是 $g$ 的倍数，所以对于每个 $g = x$，有 $x \mid y$，我们可以取 $y = x, 2x, 3x, \cdots$， 共计 $\lfloor \frac{R}{x} \rfloor $ 个；对于每个 $g = y$，有 $y \mid x$，我们可以取 $x = y, 2y, 3y, \cdots$，共计 $\lfloor \frac{R}{y} \rfloor $ 个
由于这里的 $(x, y)$ 具有对称性，所以上面二者的数量相等。
此外， $(x, x)$ 和 $(y, y)$ 有重复，因为 $g = x = y$。

于是，原问题的答案为 $\displaystyle \sum_{k = 2}^R f(k) - \sum_{x = L}^R \Big(\lfloor \frac{R}{x} \rfloor * 2 - 1\Big)$。

C++ 代码

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::vector;
using ll = long long;

int main() {
    ll l, r;
    cin >> l >> r;
    --l;

    vector<ll> f(r + 1);
    ll ans = 0;
    for (int g = r; g >= 2; --g) {
        ll w = r / g - l / g;
        f[g] = w * w;
        for (int i = g * 2; i <= r; i += g) {
            f[g] -= f[i];
        }
        ans += f[g];
    }

    for (int i = l + 1; i <= r; ++i) {
        if (i == 1) continue;
        ans -= r / i * 2 - 1;
    }

    cout << ans << '\n';

    return 0;
}