Official

E - Training Editorial by maspy

◆ 問題の書き換え

本問題において、次の記号 \(f(x), F(x), g(x), G(x)\) を用いることにします。

  • \(f(x) = A_X + x/B_X, \quad F(x) = \lfloor f(x)\rfloor\)
  • \(g(x) = A_Y + x/B_Y, \quad G(x) = \lfloor g(x) \rfloor\)

次を満たす整数 \(x\) の個数が求めるものです。

  • \(1\leqq x \leqq N\)
  • \(F(x) = G(x)\)

◆範囲の絞り込み

以下、\([L, R) = \{x\in \mathbb{R}\mid L\leqq x < R\}\) などの区間の記号を用います。

\(F(x) = G(x)\) が成り立つとき、実数 \(f(x) - g(x)\) は \(0\) に近いことが推測できると思います。このことをきちんと数式にすると、次のようになります。

  • \(f(x) \in (-\infty, g(x) - 1)\) のとき：\(F(x) = G(x)\) とはなりえない。
  • \(f(x) \in [g(x)-1, g(x))\) のとき：\(F(x) \in \{G(x) - 1, G(x)\}\) が成り立つ。
  • \(f(x) \in [g(x), g(x) + 1)\) のとき：\(F(x) \in \{G(x), G(x) + 1\}\) が成り立つ。
  • \(f(x) \in [g(x)+1, \infty)\) のとき：\(F(x) = G(x)\) とはなりえない。

これらに場合分けすることで答を計算することにしましょう。\(f(x), g(x)\) は \(x\) の \(1\) 次以下の関数なので、どのような \(x\) が \(4\) つのどれに分類されるかは簡単に計算することができます。

◆ 答えの計算

結局、次の形の問題が解ければよいと分かります：

整数 \(L, R\) が与えられる。\(L\leqq x < R\) に対して常に、\(F(x) \in \{G(x) - 1, G(x)\}\) であることが分かっている。この範囲で、\(F(x) = G(x)\) となる整数 \(x\) を数え上げよ。

\(F(x)\) や \(G(x)\) は、分かりやすい規則で扱いやすそうです。一方その差分 \(F(x) - G(x)\) には \(2\) つの周期 \(B_X, B_Y\) の規則が混在しており、扱いにくそうです。そこで、\(F(x) - G(x)\) を直接は扱わずに \(F(x), G(x)\) それぞれに独立な計算によって答えを求めることを考えます。

考察対象となる区間において \(F(x) \in \{G(x)-1, G(x)\}\) であることを考慮すると、\(F(x) = G(x)\) となる \(x\) の個数は \(\sum_{L\leqq x < R} F(x)\) および \(\sum_{L\leqq x < R} G(x)\) から計算できることが分かります。

さらに \(\sum_{L\leqq x < R} F(x) = \sum_{0\leqq x < R} F(x) - \sum_{0\leqq x < L} F(x)\) などから、最終的に次の形の式の計算に帰着されます：\(\sum_{0\leqq x < n}\left\lfloor A + \frac{x}{B}\right\rfloor\).

これは、例えば \(B\) 項ごとの区間に分けることで等差数列の和の計算に帰着できて、\(\Theta(1)\) 時間で計算することができます。

[AtCoder Library floor_sum] などの方法を利用することでも \(\Theta(1)\) 時間で計算できます（AtCoder Library の floor_sum は、\((a, m)\) に対する互除法の除算回数のループで計算されるため、\((a,m) = (1, B)\) である場合には \(\Theta(1)\) 時間となります）。

参考：https://atcoder.jp/contests/practice2/tasks/practice2_c

◆ 解答例

posted:
last update: