ABC206 E Divide Both
まず, $ 3つ条件を考えるのはややこしいので, 条件を$ 2つに減らしてみる. 具体的には, $ x < yを仮定し, 後から答えを$ 2倍することにより, $ \frac{x}{g} \neq 1の条件を考えなくてよくなる.
また, $ L = max(2, L)としてよい($ x = 1の場合, これを満たすような$ yは存在しないにも関わらず, 場合分けが必要となるため).
以上より, 問題は次のような問題に帰着された.
次の条件をすべて満たす$ L \leq x < y \leq Rの$ (x, y)の個数を求めよ.
$ x, yは互いに素でない → この条件を満たす集合を$ Aとおく.
$ yは$ xの倍数でない → この条件を満たす集合を$ Bとおく.
ここで, $ \overline{B} \subset Aであるから, $ n(A)から, $ n(\overline{B})を除いたものが答えとなる.
ただ, このままだと数えにくい. そこで$ xを$ L以上$ R以下の範囲で全探索して固定してみる. まず, この条件で, $ 2つ目の条件を満たさない$ yの個数は全体として$ O(R \log \log R)で求めることができる.
では, $ 1つ目の条件を満たす$ yの個数はどのようにして求めることができるだろうか. ここで$ f(T) := $ 1以上$ T以下の整数であって, $ xと互いに素であるものの個数 と定義すると, 求めたいものは$ f(R) - f(x - 1)と表せる. $ f(T)は「互いに素」の性質を用いると, $ Tをエラトステネスの篩を用いて素因数分解(高速素因数分解)し, 包除原理を適用することで$ O(R \log \log R)で求めることができる(実装ではbit全探索を用いるとよい).
よって, この問題を$ O(R \log \log R)で解くことができた.