以降では、\(x, y\) は \(L \leq x, y \leq R\) を満たす整数のみ考えるものとします。

\((x, y)\) の組は全部で \((R - L + 1)^2\) 個あるので、これらの内、もう一つの条件：

\(g = gcd(x, y)\) としたとき、\(g \neq 1\) かつ \(\frac{x}{g} \neq 1\) かつ \(\frac{y}{g} \neq 1\)

を満たさないものの個数を \((R - L + 1)^2\) から引くことで、答えを求めることができます。すなわち、次の条件 \((i), (ii), (iii)\) のいずれかを満たす\((x, y)\) の個数が求められれば良いです。

\((i) \, g = 1 \qquad (ii) \, \frac{x}{g} = 1 \qquad (iii)\, \frac{y}{g} = 1\)

ここで、\(A = \{ (x, y) \, | \, (x, y) は (i) を満たす\}\), \(B = \{ (x, y) \, | \, (x, y) は (ii) を満たす\}\), \(C = \{ (x, y) \, | \, (x, y) は (iii) を満たす\}\) とすると、求めたい数は \(|A \cup B \cup C|\) であり、包除原理より次が成り立ちます。ただし、\(|X|\) は集合 \(X\) の要素数を表します。

\( |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|\)

右辺のそれぞれの値を求めます。ただし、\(x, y\) についての対称性より \(|C| = |B|, \, |C \cap A| = |A \cap B|\) が成立するので、これらについては省略します。

・\(|A| = | \{ (x, y) \, | \, g = gcd(x, y) = 1 \} |\)

これは、互いに素な \((x, y)\) の個数に等しいです。公式解説の hint 4-1 のように求めることも可能ですが、次のように求めることもできます（計算量は悪化するので、高速な言語でしか間に合わないかもしれません）。

\(L \leq x \leq R\) を固定します。\(x = p_1 ^ {e_1} \dots p_k ^ {e_k} \) と素因数分解できる時、\((x, y)\) が互いに素という条件は、\(y\) が \(p_1, \dots, p_k\) のいずれの倍数でもないという条件に言い換えられます。このような \(y\) の個数は、\(p_1, \dots, p_k\) の倍数に関する包除原理を用いて \(O(2^k)\)で求めることが出来ます。エラトステネスの篩を応用することで、\(R\) 以下の整数の素因数列挙は \(O(R log log R)\) で前計算ができます。よって、合計の計算量は \(O(\sum_{L \leq x \leq R} 2^k + R log log R)\) となります。今回の制約では、\(2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \leq 10^6 <2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19\) より \(k\) の値は高々 \(7\) であるので、第一項の上界は \(2^7 \times 10^6 \fallingdotseq 1.3 \times 10^8\) 程度と見積もることが出来ます。

・\(|B| = | \{ (x, y) \, | \, g = gcd(x, y) = x \} |\)

\((g, \frac{y}{g})\) と \((x, y)\) が一対一に対応するので、\((g, \frac{y}{g})\) の組であって、\(L \leq g \leq R, \, L \leq g \times \frac{y}{g} \leq R\) を満たすものの個数を求めれば良いです。これは、各 \(g\) に対して \(\frac{y}{g}\) の個数を計算すればよいので、\(O(R)\) で求めることが出来ます。

・\(|A \cap B| = | \{ (x, y) \, | \, g = gcd(x, y) = x = 1\} |\)

\(x = 1\) より、\(L > 1\) ならば \(|A \cap B| = 0\) です。\(L = 1\) ならば、\(L \leq y \leq R\) に対して \((1, y) \in A \cap B\) であるので、\(|A \cap B| = R - L + 1\) です。

・\(|B \cap C| = | \{ (x, y) \, | \, g = gcd(x, y) = x = y \} |\)

\(L \leq g = x = y \leq R\) は全て条件を満たすので、\(|B \cap C| = R - L + 1\) です。

・\(|A \cap B \cap C| = | \{ (x, y) \, | \, g = gcd(x, y) = x = y = 1\} | \)

\(L > 1\) ならば \(0\)であり、\(L = 1\) ならば \(1\) です。

以上より答えを求めることが出来ました。ボトルネックは　\(|A|\) の計算で、\(O(\sum_{L \leq x \leq R} 2^k + R log log R)\) となります（\(k\) は \(x\) の素因数の種類数とする）。第一項の上界として見積もった値はかなり大きいですが、実際はもっと小さく、\(L = 1, R = 10^6\) の時に \(\sum_{L \leq x \leq R} 2^k = 9185685\) となります。実装方法によってはこの項が \(\sum_{L \leq x \leq R} k2^k\) となりますが、\(L = 1, R = 10^6\) に対して具体的に求めると \(32578060\) となり、これでも間に合います。

AC コード (706 ms, コメント付き) : https://atcoder.jp/contests/abc206/submissions/23635395