ABC206 E - Divide Both (500)
全てのパターンを愚直に試すと$ \mathcal{O}(R^2)で間に合わない
逆に$ \gcdがある数になる組み合わせの数を求める
$ 2 \le i \le Rなiについて大きい方から以下を行う
$ [L, R] にあるiの倍数を求める
$ v = \left\lfloor \frac{R}{i} \right\rfloor - \left\lfloor \frac{L-1}{i} \right\rfloor で求まる
iの倍数が$ \gcdになる組み合わせは$ v^2通り
この内、真に$ \gcdがiになるものを求めたいので$ \gcdがiの2倍、3倍、となっているもの全てを引く
$ L \le iだとペアの内片方が$ i自身のものが含まれてしまうので$ 2v-1を引く
全ての$ iで足した値が答え