Floor Sum Square

floor_sum_square(n, m, a, b) は、次の 3 つの和を同時に求めます。

S1 = Σ i floor((a i + b) / m)
S2 = Σ floor((a i + b) / m)^2
S3 = Σ floor((a i + b) / m)

ただし、和は i = 0 ..< n について取ります。

import

import atcoder/extra/math/floor_sum_square

使用例

import atcoder/extra/math/floor_sum_squarelet ans = floor_sum_square(5, 7, 3, 2)doAssert ans.S1 == 13doAssert ans.S2 == 6doAssert ans.S3 == 4

この例では、

floor((3i + 2) / 7) = 0, 0, 1, 1, 2

です。

戻り値

tuple[S1, S2, S3: T]

• S1: Σ i floor((a i + b) / m)
• S2: Σ floor((a i + b) / m)^2
• S3: Σ floor((a i + b) / m)

計算量

おおよそ

• O(log(n + m + a + b))

です。