Official

E - Training Editorial by evima

◆ Rephrasing the problem

Let us use the symbols \(f(x), F(x), g(x), G(x)\) as follows.

  • \(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\)

The problem asks the number of integers \(x\) that satisfies the following.

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

◆Narrowing the range

Below, we use symbols to represent intervals, such as \([L, R) = \{x\in \mathbb{R}\mid L\leqq x < R\}\).

It is not easy to guess that when \(F(x) = G(x)\), the real number \(f(x) - g(x)\) is close to \(0\). Translating this idea into formulae, we have the following:

  • When \(f(x) \in (-\infty, g(x) - 1)\): \(F(x) = G(x)\) never holds.
  • When \(f(x) \in [g(x)-1, g(x))\): \(F(x) \in \{G(x) - 1, G(x)\}\) holds.
  • When \(f(x) \in [g(x), g(x) + 1)\): \(F(x) \in \{G(x), G(x) + 1\}\) holds.
  • When \(f(x) \in [g(x)+1, \infty)\): \(F(x) = G(x)\) never holds.

Let us separately process these four cases to find the answer. Since \(f(x)\) and \(g(x)\) are functions of degree at most \(1\), we can easily find out what \(x\) goes to which of the four categories.

◆ Calculating the answer

We end up with a problem in the following form.

  • Given are integers \(L\) and \(R\). It is known that \(F(x) \in \{G(x) - 1, G(x)\}\) always holds for \(L\leqq x < R\). Count the integers \(x\) in this interval such that \(F(x) = G(x)\).

\(F(x)\) and \(G(x)\) seem to be easy to handle, while the difference \(F(x) - G(x)\) does not, since it involves a mixture of two cycles \(B_X\) and \(B_Y\). Therefore, let us avoid directly handling \(F(x) - G(x)\) and try to find the answer by separately handling \(F(x)\) and \(G(x)\).

Considering that \(F(x) \in \{G(x)-1, G(x)\}\) in our interval, we can see that we can count \(x\) such that \(F(x) = G(x)\) from \(\sum_{L\leqq x < R} F(x)\) and \(\sum_{L\leqq x < R} G(x)\).

Furthermore, using facts such as \(\sum_{L\leqq x < R} F(x) = \sum_{0\leqq x < R} F(x) - \sum_{0\leqq x < L} F(x)\), we will end up with the problem of calculating a formula in the form \(\sum_{0\leqq x < n}\left\lfloor A + \frac{x}{B}\right\rfloor\).

One approach to this is to divide the interval into smaller ones with \(B\) elements each to reduce it to calculating the sums of arithmetic sequences, which can be done in \(\Theta(1)\) time.

There are also other approaches, such as using [AtCoder Library floor_sum] to calculate it in \(\Theta(1)\) time.

Reference: https://atcoder.jp/contests/practice2/tasks/practice2_c

◆ Sample Implementation

posted:
last update: