Floor Sum (유리 등차수열 내림 합)

정의

Floor Sum 은 f(n, m, a, b) = Σ_{i=0}^{n-1} floor((a·i + b) / m) 을 O(log m) 에 계산하는 알고리즘. AtCoder Library (ACL) 의 floor_sum 함수로 표준화되었다.

분수 (a·i + b) / m 의 내림 합을 i = 0 .. n-1 에 대해 빠르게 구하는 것이 목표. n, m, a, b 가 10^18 까지 커도 수백 번의 연산으로 해결 가능.

문제 상황과 동기

단순 반복문으로 Σ floor((a·i + b) / m) 을 계산하면 O(n). n = 10^12 이상이면 사실상 불가능.

• naive: i = 0 .. n-1 순회, 매번 floor 연산. O(n).
• floor_sum: 유클리드 호제법과 동일한 재귀 구조. O(log m).

핵심 통찰: 직선 y = (a·x + b) / m 아래 격자점 (integer lattice point) 개수 로 문제를 재해석. a ≥ m 이면 몫을 분리하고, a < m 이면 x ↔ y 축 변환으로 대칭적인 하위 문제를 얻는다.

PS 에서는 정수론적 합, 조화수 근사, 디지털 논리 문제 등에서 간접적으로 등장.

시각화

핵심 아이디어

재귀적 변환. 정의 식을 그대로:

floor_sum(n, m, a, b) = Σ_{i=0}^{n-1} floor((a·i + b) / m)

Case 1: a ≥ m. 몫과 나머지로 분리.

Σ floor((a·i + b) / m) = Σ i·(a//m) + Σ floor(((a%m)·i + b) / m)
                        = (n-1)n/2 · (a//m) + floor_sum(n, m, a%m, b)

Case 2: b ≥ m. 상수항 분리.

Σ floor((a·i + b) / m) = n · (b//m) + floor_sum(n, m, a, b%m)

Case 3: a < m and b < m and a > 0. 기하 변환.

직선 y = (a·x + b) / m 아래 격자점 개수는 y 축 기준으로도 셀 수 있다. y_max = floor((a·(n-1) + b) / m).

ans = y_max · (n-1) - floor_sum(y_max, a, m, (a - 1) - (b % a))

놀랍게도 새 floor_sum 호출은 인자가 (y_max, a, m, …) 로, m 과 a 가 뒤바뀐다. 유클리드 호제법처럼 (a, m) → (m % a, a) 로 감소.

알고리즘

function floor_sum(n, m, a, b):
    ans = 0
    while true:
        if a >= m:
            ans += n * (n - 1) / 2 * (a / m)
            a %= m
            continue
        if b >= m:
            ans += n * (b / m)
            b %= m
            continue
        // a < m and b < m
        y_max = (a * (n - 1) + b) / m
        if y_max == 0:
            break
        // 변환: (n, m, a, b) ← (y_max, a, m, new_b)
        ans += y_max * (n - 1) - floor_sum(y_max, a, m, (a - 1) - (b % a))
        // 반·복·종·료 (재귀에서 이미 처리)
        break
    return ans

실제 구현은 위 loop 가 아니라 재귀. ACL 구현은 맨 처음부턴 if 문 3개를 순서대로 검사한다.

구현

// floor_sum: AtCoder library implementation
#include <bits/stdc++.h>
using ll = long long;
ll floor_sum(ll n, ll m, ll a, ll b) {
  ll ans = 0;
  if (a >= m) {
      ans += (n - 1) * n / 2 * (a / m);
      a %= m;
  }
  if (b >= m) {
      ans += n * (b / m);
      b %= m;
  }
  ll y_max = (a * (n - 1) + b) / m;
  if (y_max == 0) return ans;
  ans += y_max * (n - 1) - floor_sum(y_max, a, m, (a - 1) - (b % a));
  return ans;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int T; std::cin >> T;
  while (T--) {
      ll n, m, a, b; std::cin >> n >> m >> a >> b;
      std::cout << floor_sum(n, m, a, b) << "\n";
  }
}

# floor_sum: O(log m) with Euclidean-like recursion
def floor_sum(n: int, m: int, a: int, b: int) -> int:
  ans = 0
  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 - 1) + b) // m
  if y_max == 0:
      return ans
  ans += y_max * (n - 1) - floor_sum(y_max, a, m, (a - 1) - (b % a))
  return ans
​
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
  n, m, a, b = map(int, input().split())
  print(floor_sum(n, m, a, b))

4
2 5 3 4
5 7 2 3
100 1000 1 1
1000000000000 1000000000 123456789 987654321

2
4
5050
474889815771500499

복잡도

각 재귀에서 (a, m) 이 (m % a, a) 로 감소. 유클리드 호제법과 동일한 수렴 속도. m, a ≤ 10^18 기준 약 60~80 번 재귀.

변형 / 활용

함정

1. 128-bit 오버플로우 (C++)

(n-1) * n / 2 * (a / m) 에서 n=10^12 면 중간 곱이 5·10^23. __int128 이 필요할 수 있다. long long 은 9·10^18 까지.

2. 재귀 변환 공식의 부호

floor_sum(y_max, a, m, (a - 1) - (b % a)) 의 네 번째 인자는 (a - 1) - (b % a). ACL 코드를 복사-붙여넣기 하지 않고 증명을 이해하는 것이 중요.

3. Python 재귀 깊이

n=m=10^18 일 때 재귀 깊이가 100 전후. sys.setrecursionlimit(10**6) 정도는 안전.

BOJ 연습 문제

참고

• 유클리드 호제법
• 정수론