\[\sum_{i=1}^N \lbrack \frac{N}{i}\rbrack\]

위 식의 결과값은 어떻게 구할 수 있을까?

naive하게 구현하면 $O(N)$에 구할 수는 있지만, 훨씬 빠르게 구하는 방법이 있다.

$y=\frac{n}{x}$의 함숫값은 $x$가 커질수록 급격히 변화폭이 작아지는데, 특히 $\sqrt{n}$을 경계선으로 하면("개수"는 정수값 기준으로 함):

1. $x<\sqrt{n}$: $x$의 개수가 $\sqrt{n}$개 이하이다. (입력의 개수가 $\sqrt{n}$개 이하)
2. $x>\sqrt{n}$: $\frac{n}{x}$의 개수가 $\sqrt{n}$개 이하이다. (출력의 개수가 $\sqrt{n}$개 이하)

이는 굉장히 당연한데, $y=\frac{n}{x}$ 그래프가 $x>0$에서 $(\sqrt{n}, \sqrt{n})$ 대칭이기 때문이다. $x=\sqrt{n}$을 기점으로 이전 구간의 입력 개수가 이후 구간의 출력 개수가 됨은 당연하다.

$\lbrack \frac{N}{x} \rbrack =k$인 최대의 실수 $x=\frac{N}{k}$임을 이용해, $\lbrack \frac{N}{i} \rbrack=\lbrack \frac{N}{j} \rbrack$인 최대의 $j$는 $\lbrack \frac{N}{\lbrack \frac{N}{i} \rbrack}\rbrack$임을 알 수 있다.

따라서 $\sum_{i=1}^N \lbrack \frac{N}{i}\rbrack$는 아래 소스코드로 $O(\sqrt{N})$에 간단하게 구할 수 있다.

for(i = 1; i <= N; i = j + 1)
    j = N / (N / i)
    // 구간 길이 * 함숫값
    ans += (j - i) * (N / i)

약수 대신 배수 세기

특히, $1$부터 $N$까지 정수 $i$에 대해 $\tau(i)$, 다시 말해 약수의 개수를 모두 더하면 이것은 $\sum_{i=1}^N \lbrack \frac{N}{i}\rbrack$과 똑같다. 이를 이용해 $\sum_{i=1}^N \tau(i)$를 간단하게 구할 수 있다. 이는 어떤 수의 약수를 구하는 것보다 배수를 구하는 것이 훨씬 쉬움을 이용한 발상으로, 어떤 수의 약수를 구하는 건 좀 복잡하지만 어떤 수의 배수를 구하는 것은 $i, 2i, 3i, 4i, \ldots$으로 매우 쉽다.

\[\sum_{i=1}^N \lbrack \frac{N}{i} f(i)\rbrack\]

위와 같은 꼴도, $f(x)$가 잘 주어진다면 위 소스코드를 아래와 같이 적절히 변형하여 구할 수 있다.

for(i = 1; i <= N; i = j + 1)
    j = N / (N / i)
    // 구간 길이 * 함숫값
    // g(i, j) = f(i) + f(i + 1) + ... f(j), f가 적절히 주어진다면 g(i, j)도 빠른 시간 안에 구할 수 있을 것임
    ans += g(i, j) * (N / i)

더 자세한 설명은 아래 참고

Harmonic-Lemma

약수를 세는 것 보다 배수를 세는 게 쉽다.

잡다한 지식방

여담이지만, 처음 제시한 문제의 경우 고등학교 2학년 때 NYPC를 풀며 혼자서 겨우 풀었던 기억이 있어 굉장히 기억에 남는다. 나중에 수학 선생님한테 물어봐도 CS적인 지식이 없어서인지 $O(\sqrt{N})$에 "빨리 구하는 방법"은 모르던데..