AtCoder Library の floor_sum を使用します。

\(X_k \le k\) を満たす \(k\) の個数を数えることにします。

整数列 \(Y = (Y_0, Y_1, \dots, Y_{N-1})\) を \(\displaystyle Y_k = \left\lfloor\frac{Ak + B}{M}\right\rfloor\) で定義します。floor_sum によって \(\text{sum}(Y)\) を取得することができます。

さて、\(X_k \le k\) を満たすことは、\(\dfrac{Ak + B}{M}\) の分子から \(k + 1\) を引いたときに整数部分が変化することと同値です。

整数列 \(Y' = (Y'_0, Y'_1, \dots, Y'_{N-1})\) を \(\displaystyle Y'_k = \left\lfloor\frac{Ak + B - (k + 1)}{M}\right\rfloor\) で定義します。floor_sum によって \(\text{sum}(Y')\) を取得することができます。

以上より、\(\text{sum}(Y) - \text{sum}(Y')\) は \(X_k \le k\) を満たす \(k\) の個数と一致します。