Floor Sum
(Summation/Floor_Sum.py)

• View this file on GitHub
• Last update: 2024-12-22 15:18:10+09:00

Outline

$\displaystyle \sum_{i=K}^N \left \lfloor \dfrac{Ai+B}{M}\right \rfloor$ を高速に求めるアルゴリズム.

Theory

$\displaystyle S(A,B,M,N):=\sum_{i=0}^N \left \lfloor \dfrac{Ai+B}{M}\right \rfloor$ とする.

$A$ を $M$ で割った商と余りを $Q_A, R_A$, $B$ を $M$ で割った余りを $Q_B, R_B$ とすると,

\[\begin{align*} \left \lfloor \dfrac{Ai+B}{M}\right \rfloor &=\left \lfloor \dfrac{(Q_A M+R_A) i+(Q_B M+R_B)}{M}\right \rfloor \\ &=\left \lfloor \dfrac{(Q_A i+Q_B)M+(R_A i+R_B)}{M}\right \rfloor \\ &=\left \lfloor (Q_A i+Q_B) + \dfrac{R_A i+R_B}{M}\right \rfloor \\ &=(Q_A i+Q_B) \left \lfloor \dfrac{R_A i+R_B}{M}\right \rfloor \end{align*}\]

であるから,

\[\begin{align*} S(A,B,M,N) &=\sum_{i=0}^{N-1} \left(Q_A i+ Q_B+\left \lfloor \dfrac{R_A i+R_B}{M}\right \rfloor \right)\\ &=\dfrac{Q_A}{2} N(N-1)+Q_B N +\sum_{i=0}^{N-1} \left \lfloor \dfrac{R_A i+R_B}{M}\right \rfloor\\ &=\dfrac{Q_A}{2} N(N-1)+Q_B N +S(R_A, R_B, M, N) \end{align*}\]

となり, $0 \leq A,B \lt M$ の場合のみを考慮すれば十分であることが分かる.

以降では $0 \leq A,B \lt M$ とする.

(途中)

Contents

---

floor_sum

floor_sum(A,B,M,N)

• $\displaystyle \sum_{i=0}^{N-1} \left \lfloor \dfrac{Ai+B}{M}\right \rfloor$ を求める.

Floor_Sum

Floor_Sum(A,B,M,N,K=0)

• $\displaystyle \sum_{i=K}^{N} \left \lfloor \dfrac{Ai+B}{M}\right \rfloor$ を求める.
  • 範囲の右端が floor_sum だと開だが, Floor_Sum だと閉になっていることに注意せよ.

Verified with

• test_verify/yosupo_library_checker/Math/Floor_Sum.test.py

Code

class Floor_Sum:
    @staticmethod
    def floor_sum(A: int, B: int, M: int, N: int) -> int:
        """ sum_{i=0}^{N-1} floor((A * i + B) / M) を求める

        Args:
            A (int)
            B (int)
            M (int)
            N (int)

        Returns:
            int
        """

        total = 0
        while True:
            total += ((N - 1) * N // 2) * (A // M)
            A %= M

            total += N * (B // M)
            B %= M

            y = (A * N + B) // M
            x = B - y * M

            if y == 0:
                return total

            total += (N + x // A) * y
            A, B, M, N = M, x%A, A, y

    @classmethod
    def floor_sum_interval(cls, A: int, B: int, M: int, L: int, R: int) -> int:
        """ sum_{i=L}^R floor((A * i + B) / M) を求める

        Args:
            A (int)
            B (int)
            M (int)
            L (int)
            R (int)

        Returns:
            int
        """

        return cls.floor_sum(A, A * L + B, M, R - L + 1)

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page