Harmonic-Lemma

각 항의 역수가 등차수열을 이루는 수열을 조화수열이라고 한다. 조화수열과 연관이 있는 보조정리 Harmonic-Lemma 에 대해 알아보자.

자연수 $n$에 대하여,

$$
a_i = \left\lfloor \frac{n}{i} \right\rfloor
$$

라는 수열이 있다고 가정해보자.

실제로 값을 계산해보면, $1$부터 $n$까지 해당 값은 크게 변하지 않는 성질을 띤다.

ex) n = 16

floor(n/i)     (i : 1..16)
16, 8, 5, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1

여기서 얻을 수 있는 또 다른 성질이 있는데, 해당 수열에서 서로 다른 수의 종류는 $2\sqrt{n}$개 이하라는 점이다.

그 이유는? 해당 수열을 $\sqrt{n}$을 기준으로 나누어 살펴보자.

1) $\sqrt{n}$보다 큰 수들

$$
\left\lfloor \frac{n}{i} \right\rfloor > \sqrt{n}
$$

는

$$
\frac{n}{i} > \sqrt{n}
$$

식을 정리하면

$$
\sqrt{n} > i
$$

가 된다.

즉, $\sqrt{n}$보다 큰 수들 $i$개는 최대 개수가 $\sqrt{n}$개 정도가 된다.

2) $\sqrt{n}$보다 작거나 같은 수들

$$
\left\lfloor \frac{n}{i} \right\rfloor \le \sqrt{n}
$$

$\sqrt{n}$보다 작거나 같은 수들의 종류는 당연히 최대 개수가 $\sqrt{n}$개 정도가 될 수밖에 없다.

해당 수열의 합을 구한다고 생각해보자.

원래는 항을 하나하나씩 계산하여 $O(n)$이 걸렸지만, 같은 값이 나오는 구간은 한꺼번에 곱하여 계산하여 연산 시간을 $O(\sqrt{n})$으로 단축시킬 수 있다.

그럼 같은 값이 나오는 구간은 어떻게 구할 수 있을까?

특정 값을 $k$라고 두고,

$$
\left\lfloor \frac{n}{i} \right\rfloor = k
$$

라고 할 때, $k$가 도출될 수 있는 최대 인덱스 $i$는

$$
\left\lfloor \frac{n}{k} \right\rfloor
$$

이다. (예시를 들어 관찰하면 빠르게 알 수 있다.)

$k$가 도출될 수 있는 구간의 끝 인덱스를 $j$라고 한다면,

$$
\left\lfloor \frac{n}{j} \right\rfloor
=
\left\lfloor \frac{n}{i} \right\rfloor
$$

여야 한다. 구간 길이는 $j - i + 1$이다.

$j$는 곧 최대 인덱스이므로,

$$
j
=
\left\lfloor
\frac{n}
{\left\lfloor \frac{n}{i} \right\rfloor}
\right\rfloor
$$

이다.

같은 값이 나오는 구간 길이에

$$
\left\lfloor \frac{n}{i} \right\rfloor
$$

(즉, $k$)를 곱한다면 해당 구간의 합을 빠르게 구할 수 있다.

res = 0

i = 1
j = 0
while i <= n:
    j = n // (n // i)

    ans += (n // i) * (j - i + 1) # k가 같은 구간 합
    i = j + 1 # j까지 한번에 구했으니, i는 j 다음부터 시작

Double Counting

$$
\left\lfloor \frac{n}{i} \right\rfloor
$$

를 $n$ 이하에서 $i$의 배수 개수라고 생각해보자.

$1$ 이상 $n$ 이하의 $i$의 배수를 구한다는 것은 약수의 현황을 알 수 있다는 것과 동일하다.

Double Counting을 활용하여, 약수를 구하는 것보다 배수를 구하는 것이 더 쉽다라는 아이디어를 사용하면 약수의 개수 및 합을 $O(n)$으로 빠르게 구할 수 있다.

약수의 개수 : $[i, j]$ 구간의 약수들이 $1$ 이상 $n$ 이하에서

$$
\left\lfloor \frac{n}{i} \right\rfloor
$$

번 등장한다.

약수의 합 : 약수의 개수를 구할 때, $[i, j]$ 약수들의 실제 합과 같이 더해주면 된다.

학습 출처 : https://ahgus89.github.io/algorithm/Harmonic-Lemma/