核心概述
在给定 n、m、a、b 的条件下，使用“参数互换/辗转缩减”法以 O(log(max(a,m))) 时间计算 Σ⌊(a·i+b)/m⌋ 以及由恒等式导出的取模求和，适合超大 n 的批量取模场景。
原文引述
Description: Compute Σ floor((a i + b)/m) for i∈[0,n) in O(log(max(a,m))) (AtCoder/KACTL floor_sum). The sum of remainders follows from identity. Time: O(log(max(a,m))) (amortized)
展开阐述
-
函数/接口（据实现）
- long long floor_sum(long long n, long long m, long long a, long long b)
- 返回 S_floor = Σ_{i=0}^{n-1} ⌊(a·i + b)/m⌋。
- long long mod_sum(long long n, long long m, long long a, long long b)
- 返回 S_mod = Σ_{i=0}^{n-1} ((a·i + b) mod m)。
- 可由恒等式快速得到：S_mod = n·b + a·n·(n-1)/2 − m·floor_sum(n,m,a,b)。
- long long floor_sum(long long n, long long m, long long a, long long b)
-
核心恒等式
- 分解：(a·i + b) = m·⌊(a·i + b)/m⌋ + ((a·i + b) mod m)。
- 对 i 求和：Σ(a·i+b) = m·S_floor + S_mod。
- Σ(a·i+b) = a·n·(n−1)/2 + b·n。
- 故 S_mod = a·n·(n−1)/2 + b·n − m·S_floor。
-
算法（迭代版 floor_sum，参数互换）
- 令 res=0。循环处理直到 (a·n + b) < m：
- 若 a ≥ m：res += (a/m) * n*(n−1)/2；a %= m。
- 若 b ≥ m：res += (b/m) * n；b %= m。
- 令 y = (a*n + b) / m（当前最高可达商值），若 y==0 则返回 res。
- 令 b’ = (a*n + b) % m；交换 a 与 m，并将 n ← y，b ← b’，继续。
- 该过程实质是对 (a,m) 做“互换与缩小”，复杂度与辗转相除法同阶。
- 令 res=0。循环处理直到 (a·n + b) < m：
-
输出语义
- floor_sum 返回 S_floor。
- mod_sum 返回 S_mod；在需要同时得到两者时，先算 floor_sum 再套用恒等式即可。
-
复杂度
- 每次迭代都会减小参数规模，近似 O(log(max(a,m)))；常数小，适合超大 n 的批量求和。
-
使用与注意
- 参数需为 0 ≤ a,b,m，n ≥ 0，且 m > 0；实现中注意 64 位溢出，n*(n−1)/2 及乘法用 128 位中间量更稳妥（参见 090-数论-长整型模乘）。
- 该模板常作为许多“分块/数论和”子程序（如整除分块、前缀和取模）基础，避免 O(n)。
- 若仅需 S_mod，可直接用恒等式并确保先取模与溢出防护。