Day 156-Q1 | floor_sum（類ユークリッド算法）

問題

非負整数 $N,M,A,B$ が与えられる。次の値を求めよ。

$$S(N,M,A,B)=\sum_{i=0}^{N-1}\left\lfloor\frac{A\,i+B}{M}\right\rfloor$$

幾何的には、直線 $y=(Ax+B)/M$ の下側（$y\ge1$ の部分）にある格子点を $x=0,\dots,N-1$ の各列で数えた総数である。$N$ が $10^9$ 規模のため、$i$ を1つずつ回す $O(N)$ の全探索は間に合わない。

入力形式

T
N_1 M_1 A_1 B_1
...
N_T M_T A_T B_T

制約

変数	範囲	補足
$T$	$1\le T\le 10^5$	クエリ数
$N$	$1\le N\le 10^9$	項数（全探索不可）
$M$	$1\le M\le 10^9$	分母
$A,B$	$0\le A,B<M$	模範解答は $A,B\ge M$ でも動く

入出力例

入力例1

4
4 10 6 3
6 5 4 3
1 1 0 0
31415 92653 58979 32384

出力例1

1件目: $\lfloor3/10\rfloor+\lfloor9/10\rfloor+\lfloor15/10\rfloor+\lfloor21/10\rfloor=0+0+1+2=3$。

概念図：列で数える vs 行で数える（$N=4,M=10,A=6,B=3$）

ヒント（段階的開示）

ヒント1（方向性）

$A\ge M$ や $B\ge M$ の部分は「商」として先に外へ出せる（$\lfloor(Ai+B)/M\rfloor=\lfloor A/M\rfloor i+\lfloor B/M\rfloor+\lfloor((A\bmod M)i+(B\bmod M))/M\rfloor$）。残るのは $0\le A,B<M$ の場合だけ。この「割って余りを取る」操作の繰り返しはユークリッドの互除法の形をしている。

ヒント2（アプローチ）

$0\le A,B<M$ のとき、格子点を列ごとではなく行ごとに数え直す。$y_{\max}$ を最上段とし、各 $y$ について「$(Ai+B)/M\ge y$ となる $i$ の個数」を足すと、$\sum_j\lfloor(Mj+c)/A\rfloor$ という同じ形で $(M,A)$ の役割が入れ替わった問題になる。分母が $A<M$ に縮むので、互除法と同じ速さで収束する。

ヒント3（誘導）

def floor_sum(n, m, a, b):
    ans = 0
    while True:
        if a >= m:
            ans += (n - 1) * n // 2 * (a // m); a %= m
        if b >= m:
            ans += n * (b // m); b %= m
        y_max = a * n + b
        if y_max < m:
            break
        n, b, m, a = y_max // m, y_max % m, a, m
    return ans

模範解答 (Python)

import sys

def floor_sum(n: int, m: int, a: int, b: int) -> int:
    """sum_{i=0}^{n-1} floor((a*i + b) / m)  （ACL floor_sum と同じ再帰構造）"""
    ans = 0
    while True:
        # 商の部分を先に取り出す（等差数列の和 / 定数×n）
        if a >= m:
            ans += (n - 1) * n // 2 * (a // m)
            a %= m
        if b >= m:
            ans += n * (b // m)
            b %= m
        # 0 <= a, b < m の状態。y_max = a*n + b が m 未満なら床はすべて 0
        y_max = a * n + b
        if y_max < m:
            break
        # 行方向に数え直すと (n, m, a, b) -> (y_max//m, a, m, y_max%m)
        n, b, m, a = y_max // m, y_max % m, a, m
    return ans

def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    idx = 1
    for _ in range(t):
        n, m, a, b = map(int, data[idx:idx + 4])
        idx += 4
        out.append(floor_sum(n, m, a, b))
    sys.stdout.write("\n".join(map(str, out)) + "\n")

main()

Step-by-Step 解説

1商を先に外へ出す
$A=qM+a'$ と分ければ $\lfloor(Ai+B)/M\rfloor=qi+\lfloor(a'i+B)/M\rfloor$。$i=0..N-1$ で足すと $q\cdot\frac{(N-1)N}{2}$ が確定分、$B$ 側は $N\lfloor B/M\rfloor$。先にやる理由：後段の行方向カウントは $0\le A,B<M$ を前提にしないと $y_{\max}$ の見積もりが崩れる。

2行方向カウントで「同じ形」に落とす
$Ai+B\ge My\iff i\ge\lceil(My-B)/A\rceil$ なので、各 $y$ の個数は $N-\lceil(My-B)/A\rceil$。$\lceil x/A\rceil=\lfloor(x+A-1)/A\rfloor$ で書き換えると $\sum_j\lfloor(Mj+c)/A\rfloor$ になり $(M,A)$ が入れ替わる。$A<M$ なので分母が縮み、次の反復で $M\bmod A$ まで落ちる——互除法と同じ収束性。

3実測（本ページ作成時に Python で実行）

入力 $(N,M,A,B)$	floor_sum	$O(N)$ 全探索	ループ回数
(4,10,6,3)	3	3	4
(6,5,4,3)	13	13	3
(1,1,0,0)	0	0	1
(31415,92653,58979,32384)	314095480	314095480	12
$(10^9,998244353,10^9-7,123456789)$	500879362975304130	未実行（$10^9$ 回は非現実的）	13

乱択 2000 ケース（$N,M\le50$, $A,B\le100$）で全探索と不一致 0 件。ループ 12〜13 回は $\log_\phi 10^9\approx43$ の上界よりかなり小さいが、互除法の最悪ケース（連続フィボナッチ数）を入力に含めていないため「常に十数回」とは一般化できない。

迷った他案と採らなかった理由

案	採否	理由
$O(N)$ 全探索	却下	$N=10^9,T=10^5$ で $10^{14}$ 回
再帰関数で書く	却下（ループ採用）	深さは $O(\log)$ で問題ないが、Python の関数呼び出しコストと再帰上限設定を避けた。ACL 本家もループ
y_max=(a*(n-1)+b)//m の古典形	同値	ACL は a*n+b で行数と余りを一度に取り出す。本ページは「ライブラリと同じ形」を優先
C++ で unsigned long long	Python では不要	多倍長整数なので $(n-1)n/2\cdot(a/m)$ が $10^{27}$ 規模でも安全。C++ 移植時に最初に壊れる箇所

よくあるミス

ミス	原因	正しい書き方
$A\ge M$ の処理を忘れ $y_{\max}$ の見積もりが破綻	行方向カウントは $0\le A,B<M$ 前提	ループ先頭で必ず a %= m, b %= m
入れ替え代入の順序ミス	4変数同時代入の対応ずれ	(y_max//m, y_max%m, a, m) の順を固定
終了条件を y_max <= m にする	$y_{\max}=M$ ちょうどで床 1 の項が残る	if y_max < m: break
C++ 移植で long long オーバーフロー	$(n-1)n/2\cdot(a/m)$ が $2^{63}$ 超	ACL 同様 unsigned long long

次のステップ

関連する実問題: ACL Practice Contest C — Floor Sum（入力例1は同問題のサンプル値で検証）
発展: $\sum_i\lfloor(Ai+B)/M\rfloor^2$ や $\sum_i i\lfloor(Ai+B)/M\rfloor$ を同じ再帰で同時に求める一般化類ユークリッド
扱わなかった範囲: 負の $A,B$ への拡張（正規化で帰着できるが制約外とした）
次回予告: 五角数定理による分割数（$O(N\sqrt N)$）

自己評価

完全理解おおむね理解要復習

Day 156-Q1 — floor_sum（類ユークリッド算法・床関数の総和）

問題