[BOJ] 백준 15897. 잘못 구현한 에라토스테네스의 체 (Gold II) Harmonic_Lemma

문제

https://www.acmicpc.net/problem/15897

15897번: 잘못 구현한 에라토스테네스의 체

꽤 어렵게 다가온 수학문제이다.

N이 1e9이므로 O(N)은 시간초과가 발생한다.

어떻게 해결해야 할까?

---

Harmonic Lemma (조화수열의 성질)

예시로 N=6인 경우를 들어보자.

j의 값은 i의 값이 더해지므로, i의 값이 횟수에 영향을 준다.

맨 처음에 j는 디폴트값으로 1이므로, 1+(N-1)/i의 값이 횟수가 됨을 확인할 수 있다.

그러나, 아직까지는 아래 O(N) 코드밖에 구현이 불가능하다.

// O(N)
for(int i=1;i<=N;i++){
    // 1, 1+i, 1+2*i, 1+3*i, ... 
	ans += 1 + (N-1)/i;
}

어떻게 하면 시간복잡도를 줄일 수 있을까?

잘 생각해보면 횟수가 같은 경우끼리는 O(1)에 계산을 끝낼 수 있다.

바로 조화수열의 성질 (harmonic lemma)를 이용하면 가능하다!

 

(N-1)까지 1의 배수의 개수는 N-1개.

(N-1)까지 2의 배수의 개수는 (N-1)/2개.

(N-1)까지 3의 배수의 개수는 (N-1)/3개.

.

.

.

(N-1)까지 k의 배수의 개수는 (N-1)/k개이다.

 

즉, (N-1)/k 의 값이 같은 것끼리의 범위를 구해놓으면 된다.

예를 들어 N=6일 때, (6-1)/3 = (6-1)/4 = (6-1)/5 이고, 이 때 k=3이므로 ans += k * (6-1)/5를 하면 i=3,4,5일 때의 계산을 O(1)에 한 번에 할 수 있다. 

 

자세한 성질은 아래 블로그 포스팅을 보자.

https://ahgus89.github.io/algorithm/Harmonic-Lemma/

Harmonic-Lemma

이렇게 하면 Harmonic_Lemma 성질에 의해 

O(sqrt(N))에 해결할 수 있다.

N/i이 같은 구간이 존재하기 때문에, 서로 다른 N/i 의 개수는 2sqrt(N)개를 넘지 않기 때문이다.

자세한 증명은 위 블로그를 참고하자.

---

코드

#include <iostream>
typedef long long ll;
using namespace std;
ll N;
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N;
	ll j = 1, ans = N;
	for (ll i = 2; i < N; i = j + 1) {
    		// (N-1)/i 가 같은 범위의 최댓값
		j = (N - 1) / ((N - 1) / i);
        	// (N-1)/i 일 때, 더해지는 횟수
		ll cnt = 1 + (N - 1) / i;
		ans += (j - i + 1) * cnt;
	}
	if (N != 1)
		ans++;
	cout << ans << "\n";
}