\( L=1 \)の場合は\( L=2\)としても答えは変わらないので制約は\(2≤L≤R≤10^6\)としてよいです。

求める数は

\( f_1(L,R)=\#\{(x,y)|L≤x<y≤R\} \)

\( f_2(L,R)=\#\{(x,y)|L≤x<y≤R∧gcd(x,y)=1\} \)

\( f_3(L,R)=\#\{(x,y)|L≤x<y≤R∧x|y\} \)

(ただし\(\#A\)で\(A\)の要素の個数を表すとし、\(x|y\)は\(y\)が\(x\)の倍数であることを表す。) として、

\(2( f_1(L,R)-f_2(L,R)-f_3(L,R))\)

です。(\(2≤L\)の条件から\(f_2(L,R)\)と\(f_3(L,R)\)に重複はありません。)

\( f_2(L,R) \)以外は、

\(f_1(L,R)=comb(R-L+1,2)\)

\(f_3(L,R)=∑_{i=L}^{R}(\lfloor\frac{R}{i}\rfloor-1)\)

で求まります。 ここでは\( f_2(L,R) \)の求め方の別解について述べます。

\( f_2(L,R) \)は\( f_1(L,R) \)から最大公約数が2以上の組を抜いたものと考えることができ、最大公約数が \(i\)の組 \((x,y)\)の数は \((\frac{x}{i},\frac{y}{i})\)が互いに素になることをふまえると、 \(f_2(\lfloor\frac{L-1}{i}\rfloor+1,\lfloor\frac{R}{i}\rfloor)\)で求まるから、

\( f_2(L,R) =f_1(L,R)-∑_{i=2}^{R} f_2(\lfloor\frac{L-1}{i}\rfloor+1,\lfloor\frac{R}{i}\rfloor)\)

よって、\( f_2(L,R) \)は \(L=R\)の場合に帰着し、このとき\( f_2(L,R)=0\)となります。

このままでは再帰回数が膨大になるのでTLEになりますが、引数として現れるのは \(f_2(\lfloor\frac{L-1}{i}\rfloor+1,\lfloor\frac{R}{i}\rfloor),(1≤i≤R)\)の高々\(R\)通りなのでメモ化再帰することで解けました。