[AtCoder] ABC 131 C – Anti-Division

問題

方針

範囲内の \( C \) かつ \( B \) で割り切れるものの数を求めて、全体から引けばよいです。どのように求めるかというと、範囲内の \( C\) と \(D \) の倍数の個数から \( C, D \) の最小公倍数の個数を引けばよいです。

区間に存在する \( g \) 倍数の個数

区間 \([l, r] \) に \( g \) の倍数が含まれる個数 \( k \) は、

\[ k = \lfloor \dfrac{r + g}{g}\rfloor – \lfloor \dfrac{l +g – 1}{g}\rfloor \]

と表すことができます。

コード