PS를 위한 수학 - Harmonic Lemma

조화 수열

조화 수열은 다음과 같이 전개되는 꼴의 식을 의미한다.

$$ \Bigl[\frac N1 \Bigr],\ \Bigl[\frac N2 \Bigr],\ \Bigl[\frac N3\Bigr]\ \cdots \ \Bigl[\frac Nn\Bigr] $$

이 수열은 PS에서 꽤나 자주 등장하는데, 이걸로 직접 문제를 풀거나 시간복잡도를 분석하는 등 써먹을 것이 많기 때문이다.

예를 들어, 에라토스테네스의 체를 보자.

const int MAX = 1e2;
vector<bool> is_prime(MAX + 1, true);
vector<int> primes;
for (int i = 2; i <= MAX; i++) {
   if (!is_prime[i]) continue;
   primes.push_back(i);
   for (int j = i + i; j <= MAX; j += i)
      is_prime[j] = false;
}

이런 코드가 있다고 할 때, $i=k$ 라면 안쪽의 for문 반복 횟수는 대략 $\left[\dfrac Nk\right]$번 이다.

물론 에라토스테네스의 체는 이미 소수가 아닌 수일 경우 반복문을 반복하지 않기 때문에 시간복잡도적인 측면에서 큰 상관이 없지만 그래도 이러한 느낌을 가져간다고 할 수 있다.

시간복잡도

$\quad \displaystyle \sum_{i=1}^N \left[ \dfrac Ni \right]$ 를 구한다고 해보자. 이것의 시간복잡도는 얼마일까?

naive하게 구하면 $O(N)$ 이지만, 여기서 중요한 테크닉이 나오는데, $i$에 대해 하나하나 구해주는 것이 아닌, $\left[\dfrac Ni\right]$가 동일한 값을 가진 구간들의 길이를 세는것이다.

$\left[\dfrac Ni\right]=k$ 의 값을 가지는 가장 큰 실수 $i$는 $\dfrac Nk$ 이다.

그러면 이 구간에서의 가장 큰 정수는 $\left[\dfrac Nk\right]$이다.

그러므로 $\left[\dfrac Ni \right]=\left[\dfrac Nk \right]$ 가되기 위한 최대 정수 $i$는 $\color{salmon} \biggl[ \dfrac {N}{\left[ \frac Nk \right]} \biggr]$ 이다.

코드로 보면,

int N = 100;  
  
for (int l = 1, r; l <= N; l = r + 1) {  
   int k = N / l;  
   r = N / k;  
   debug(l, r, k);  
}

1, 1, 100
2, 2, 50
3, 3, 33
4, 4, 25
5, 5, 20
6, 6, 16
7, 7, 14
8, 8, 12
9, 9, 11
10, 10, 10
11, 11, 9
12, 12, 8
13, 14, 7
15, 16, 6
17, 20, 5
21, 25, 4
26, 33, 3
34, 50, 2
51, 100, 1

처럼 나온다.

구간을 $O(1)$에 구할 수 있으므로 구간들의 개수가 결국 시간 복잡도와 연관이 있다는 뜻이다.

결론적으로 이 구간의 개수는 $\color{salmon} O(2\sqrt N)$ 인데, 그 이유를 살펴보자.

1. $i<\sqrt N$ 일 때,

어차피 $i$가 $\sqrt N$ 개보다 적으므로 $O(\sqrt N)$ 이다.

1. $i \geq \sqrt N$ 일 때

$\left[ \dfrac Ni \right]$ 의 값 자체가 조건에 의하여 $\sqrt N$ 개를 넘을 수 없으므로 $O(\sqrt N)$ 이다.

따라서 $O(2\sqrt N)$ 이다.

약수의 개수, 약수의 합 세기

이건 정수론에서 $\tau$ 와 $\sigma$ 를 의미하는 것이므로 특정 숫자에 대해서만 구한다면 소인수분해하여 공식을 활용해줄 수도 있다.

$n=p_1^{k_1}+p_2^{k_2}+\cdots+p_m^{k_m}$

$\tau_n=\displaystyle \prod_{i=1}^m (k_i+1)$

$\sigma_n=\displaystyle \prod_{i=1}^m \dfrac{p_i^{k_{i+1}}-1}{p_i-1}~~(등비수열 공식)$

그러나 특정 구간의 모든 수들에 대해서의 $\tau$와 $\sigma$ 의 합은 조화 수열의 합으로 구할 수 있다.

이건 수들의 약수의 개수를 모두 세서 더해주는 방식이 아닌 범위 내에서의 배수의 개수를 세서 모두 더해주는 방법으로 치환하여 구할 수 있다.

어떤 수 $k$의 $n$ 이하에서의 배수의 개수는 $\left[\dfrac nk\right]$ 인데,

$[l, r]$ 구간에서의 배수의 개수는 $\Bigl[ \dfrac rk \Bigr] - \Bigl[ \dfrac {l-1}k \Bigr]$ 이다.

이는 결국 $\displaystyle \sum_{i=1}^N \left[ \dfrac Ni \right]$ 이기 때문이다.

즉 이 식이 의미하는건 $N$ 이하에서의 수들의 약수의 개수의 총합이다.

약수의 합(=배수의 합)도 다르지 않다.

$\quad \displaystyle \sum_{i=1}^N i\left[ \frac Ni \right]$ 를 계산해주면 된다.

이러한 꼴은 지금처럼 $\displaystyle \sum_{i=1}^N \left[ \dfrac Ni \right]$ 꼴과 다르게 $\displaystyle \sum_{i=1}^N f(x)\left[ \dfrac Ni \right]$ 가 된 꼴이라고 볼 수 있는데, 이 경우 $\left[ \dfrac Ni \right]=k$ 인 구간 $[l, r]$에서 $\displaystyle \sum_{i=l}^r f(i)$ 를 $\left[ \dfrac Ni \right]$ 에 곱해주는 것으로 $O(N)$ 이 아닌 $\color{salmon} O(\sqrt N)$ 에 문제를 해결할 수 있도록 해준다.

물론 여기에 $\displaystyle \sum_{i=l}^r f(i)$ 를 구하는 시간복잡도는 별도로 곱해진다.

배수를 구하는 것은 $\quad \displaystyle \sum_{i=1}^N i\left[ \frac Ni \right]$ 를 구하는 것이라고 했고, $\displaystyle \sum_{i=l}^r i$는 $\dfrac {r(r+1)}2-\dfrac{l(l-1)}2=\dfrac {(r-l+1)\cdot(r+l)}2$ 이므로 $O(1)$에 구해진다.

연습 문제들

BOJ 15897 - 잘못 구현한 에라토스테네스의 체

코드를 보면 $j=i$ 로 초기화 되는것이 아니라서 온전히 조화수열의 합이 정답이 아니기 때문에 일단 $j=1$ 일 때의 모든 수들의 정답인 $N$ 개를 정답에 더해주고, $N \coloneqq N-1$ 로 바꿔준다음 문제를 풀면 된다.

마치 $j=0$ 부터 시작시키는 것으로 바꾸어 주었다고 생각하면 된다.

void solve() {  
   int N;  
   cin >> N;  
   ll ans = N;  
   N--;  
   for (int l = 1, r; l <= N; l = r + 1) {  
      int k = N / l;  
      r = N / k;  
      ans += 1ll * (r - l + 1) * k;  
   }  
   cout << ans;  
}

BOJ 17417 - Optimization is Freaky Fun

---

References

ahgus89님 블로그