\(x,y\) の最大公約数 \(g\) の値ごとに組の個数を求めることを考えます。

まずは \(\frac{x}{g}\neq 1,\ \frac{y}{g}\neq 1\) の条件を忘れて、\(g\neq 1\) の条件だけを考えてみましょう。

問題：\(k=2,3,\ldots,R\) のそれぞれについて、\(\gcd(x,y)=k\) となる \(L\leq x,y\leq R\) の組の個数を求めよ

この問題は ABC162E Sum of gcd of Tuples (Hard) とほとんど同様にして次のように解くことができます。

\(\gcd(x,y)\) が \(k\) の倍数 であるための必要十分条件は、\(x,y\) がともに \(k\) の倍数であることです。\(L\) 以上 \(R\) 以下の \(k\) の倍数の個数は \(X_k:=\left\lfloor\frac{R}{k}\right\rfloor-\left\lfloor\frac{L-1}{k}\right\rfloor\) なので、\(\gcd(x,y)\) が \(k\) の倍数 になるような \(L\leq x,y\leq R\) の組の個数は \(X_k^2\) です。
\(\gcd(x,y)\) がちょうど \(k\) であるための必要十分条件は、「\(\gcd(x,y)\) が \(k\) の倍数であり、かつ、\(2k,3k,\ldots\) ではない」ことです。したがって、これは \(k\) が大きな方から順に計算することで求められます。

最後に、これらのうち \(\frac{x}{g}\neq 1,\ \frac{y}{g}\neq 1\) の条件を満たさない組の個数を求めて引くことを考えましょう。

「\(\gcd(x,y)=g\) かつ『\(\frac{x}{g}\neq 1,\ \frac{y}{g}\neq 1\) のどちらかを満たさない』」は「\(\gcd(x,y)=g\) かつ『\(x=g\) または \(y=g\)』」と同値です。\(x,y\) はともに \(g\) の倍数なので、このような組は \(\max(2,L)\leq g \leq R\) のとき\(2X_g-1\) 組あり、そうでないとき存在しません。

以上により問題を解くことができました。\(\gcd(x,y)=k\) となる組の個数を求める部分の計算がボトルネックとなり、計算量は \(O(R\log R)\) です。