もう少し簡単な類題で慣れないと解けないなぁ，という感想．
とりあえず約数で考えて，余分なものを差し引いて最大公約数の寄与だけ取り出す方法は汎用性がありそう．
考えたこと
与えられている条件は- $x,y$が互いに素ではなく
- 一方が他方の倍数でない
倍数を順にカウントしていけばできそう．計算量はエラトステネスの篩-likeに処理して$O(N\log N)$でできそう，という方針で考えた．
AtCoder - 解法の整理 - 競プロはじめました
しかし，余分にカウントした分をうまく除く方法を思いつけず，タイムアウト．
解法
わかりやすいコードを参考に，考察する．解法
Submission #23587175 - AtCoder Beginner Contest 206（Sponsored by Panasonic）（公式解説とほぼ同じ）$ x < y$として考えて，最後に答えを2倍する．
dp[i]
- 区間$[L,R]$にある$i$の倍数の個数$=\lfloor R/i \rfloor - \lfloor (L - 1)/i \rfloor$
- ↑から2つ選ぶ方法の数
- ↑から
dp[j]($j = 2i, 3i, ...$) を除くことで，$i$が最大公約数のときの寄与だけを取り出す．
dp[i]$=$ (区間$[L,R]$にある$i$を最大公約数とする2数$x,y$を選ぶ方法の数) となっている．ans
ans$=\sum_{i = 2}^{R} \mathrm{dp\,}[i]$- ↑から$x=i$となる場合の数を除く．これは$i \mid y$（$y$が$i$の倍数）の場合を意味する．したがって，$[L,R]$にある$i\neq 1$の倍数の個数から，$x$として使う1つ分を除いたものを足し合わせた$\sum_{i=\max(2,L) }^{R} \lfloor R / i\rfloor - 1$である．
