조화수 (Harmonic Number)

정의

조화수 (Harmonic Number) H_n 은 자연수 n 에 대해 역수의 합 Σ_{k=1}^{n} 1/k 으로 정의. 점근적으로 H_n = ln n + γ + 1/(2n) - ... (γ ≈ 0.5772, 오일러-마스케로니 상수). 정수론과 알고리즘 분석에서 O(n log n) 의 log factor 가 사실은 H_n 에서 비롯.

문제 상황과 동기

n = 10^6 일 때 Σ_{k=1}^{n} ⌊n/k⌋ 또는 약수 배수 관계의 합.

• naive (이중 루프): O(n²). n=10^5 면 10^10, 불가능.
• 조화수 통찰: n/k 의 서로 다른 값은 O(√n) 개. 구간 나누기로 O(√n) 또는 O(n log n).

핵심 통찰: ⌊n/k⌋ 는 k 가 작을 때는 자주 변하지만, k 가 클 때는 천천히 변한다. 따라서 같은 몫을 갖는 구간 을 한 번에 처리할 수 있다.

시각화

핵심 아이디어

조화수 점화

H_0 = 0
H_n = H_{n-1} + 1/n

구간 나누기 (harmonic lemma)

⌊n/k⌋ 의 값이 같은 k 의 구간 [l, r]:

r = n / (n / l)

이 구간 내에서 ⌊n/k⌋ = q 로 일정. 합을 q × (r - l + 1) 로 O(1) 에 계산.

이 기법은 각 구간을 묶어서 O(√n) 번의 연산으로 모든 ⌊n/k⌋ 의 합을 구하게 해 준다.

약수 배수 합

Σ_{i=1}^{n} d(i) = Σ_{i=1}^{n} ⌊n/i⌋ = 2 Σ_{i=1}^{√n} ⌊n/i⌋ - (⌊√n⌋)²

알고리즘

harmonic_sum(n):
    sum = 0
    for i = 1..n:
        sum += 1.0 / i
    return sum

harmonic_floor_sum(n):        # Σ ⌊n/i⌋
    sum = 0
    l = 1
    while l <= n:
        q = n // l
        r = n // q
        sum += q * (r - l + 1)
        l = r + 1
    return sum

구현

// H_n 계산 + harmonic floor sum O(sqrt(n))
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
double harmonic(int n) {
  double h = 0;
  for (int i = 1; i <= n; i++) h += 1.0 / i;
  return h;
}
​
ll floor_sum(ll n) {
  ll sum = 0;
  for (ll l = 1, r; l <= n; l = r + 1) {
      ll q = n / l;
      r = n / q;
      sum += q * (r - l + 1);
  }
  return sum;
}
​
int main() {
  int n; cin >> n;
  cout << fixed << setprecision(10);
  cout << "H_" << n << " = " << harmonic(n) << "\n";
  cout << "Sigma n/i = " << floor_sum(n) << "\n";
  return 0;
}

# H_n (float) + harmonic floor sum O(sqrt(n))
def harmonic(n):
  h = 0.0
  for i in range(1, n + 1):
      h += 1.0 / i
  return h
​
def floor_sum(n):
  s = l = 0
  while l < n:
      l += 1
      q = n // l
      r = n // q
      s += q * (r - l + 1)
      l = r
  return s
​
import sys
n = int(sys.stdin.readline())
print(f"H_{n} = {harmonic(n):.10f}")
print(f"Sigma n/i = {floor_sum(n)}")

10

H_10 = 2.9289682540
Sigma n/i = 27

1000000

H_1000000 = 14.3927267229
Sigma n/i = 13970034

복잡도

변형 / 활용

함정

1. 부동소수점 정밀도

H_n 은 float/double 로 n ≥ 10^7 이면 오차 누적. 큰 n 에 대해서는 log(n) + γ 근사식 사용.

2. 64-bit 오버플로우

floor_sum(n) 에서 n=10^12 면 q * (r-l+1) 이 long long 초과 가능. unsigned long long 또는 __int128 필요.

3. 구간 경계 실수

l = r + 1 에서 l 이 n+1 이면 루프 종료. r = n / (n / l) 에서 n / l == 0 이면 0으로 나누기 방지: l > n 이면 break.

BOJ 연습 문제

참고

• 에라토스테네스의 체 (약수 관련)
• 뫼비우스 함수 (반전 공식)
• 포함 배제의 원리