計算量がよくわかりませんが、なぜかACできてしまったので書きます。(公式解説を見たら同じような解法が載ってました)

解法

問題の条件を言い換える。
まず、条件を満たす $x, y$ の組み合わせは、( $x = y$ であるような場合をさておくと)対称になるので、 $x$ と $y$ の関係はとりあえず $x \le y$ としてよい。
さらに、 $x / gcd(x, y) \neq 1$ から、 $x \neq gcd(x, y)$ でなく、したがって $x \neq y$ であるので、条件は $x \lt y$ とすることができる。この条件下の解が出れば、これを2倍することで元の問題の解になる。

また、 $x \neq y$ から、 $y = gcd(x, y)$ となることはないので、条件のうち、 $y / gcd(x, y) \neq 1$ は削ることができる。
したがって、問題の条件は $gcd(x, y) \neq 1$ かつ $x / gcd(x, y) \neq 1$ になる。
さらに言い換えると、 $gcd(x, y) = 1$ または $x / gcd(x, y) = 1$ であるような $(x, y)$ の組み合わせが求まれば、全体からこれを引けば解がでるので、以降これを求めることとする。

これを求めるには、 $x$ を範囲中全探索し、 $x$ と互いに素な $y$ ( $gcd(x, y) = 1$ から)、あるいは $x$ の倍数である $y$ ( $x / gcd(x, y) = 1$ から)、の2つを求めて足しこめばよい。
後者については簡単に求められる。( $R / x - 1$ です)
前者については、 $x$ の約数の倍数でないような数を求めればよいが、実際には約数の倍数ではなく、素因数の倍数で十分である。 $x$ の素因数は $2 * 3 * 5 * 7 * 11 * 13 * 17 \lt 10 ^ 6 \lt 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19$ であることから最大でも $7$ 個程度なので、包除原理を用いることで、区間 $(x, R$ ]の中で $x$ の素因数の倍数でない数を求めることができる。

これらを足し込んだ結果は、 $x \lt y$ の条件において、元の問題で与えられた条件を満たさない場合の数であるので、 $x, y$ のすべての組み合わせである $(R - L + 1) ^ 2$ からこれを $2$ 倍して引き、さらに $x = y$ の場合は元の問題の条件を満たさない( $gcd(x, y)$ で割ると $x, y$ ともに $1$ となる)ため、 $R - L + 1$ を引いた数が最終的な解となる。