harmonic lemma 응용하기 - 올림으로 된 조화수열 합을 빠르게 구하는 방법

1. 문제

 

15897번: 잘못 구현한 에라토스테네스의 체 (acmicpc.net)

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

 

2. 풀이

 

다음에서 6번줄이 몇번이나 실행되는지 구하는 문제

 

int n;
cin >> n;
int* sieve = new int[n+1];
for (int i = 1; i <= n; i++){
    for (int j = 1; j <= n; j+= i){
        sieve[j] += 1;
    }
}

 

n = 12라고 할 때,

 

i = 1인 경우 j = 1,2,3,4,5,6,7,8,9,10,11,12로 12번

 

i = 2인 경우 j = 1,3,5,7,9,11 6번

 

i = 3인 경우 j = 1,4,7,10 4번

 

i = 4인 경우 j = 1,5,9 3번

 

i = 5인 경우 j = 1,6,11 3번

 

i = 6인 경우 j = 1,7 2번

 

i = 7인 경우 j = 1,8 2번

 

i = 8인 경우 j = 1,9 2번

 

i = 9인 경우 j = 1,10 2번

 

i = 10인 경우 j = 1,11 2번

 

i = 11인 경우 j = 1,12 2번

 

i = 12인 경우 j = 1 1번

 

그래서 12 + 6 + 4 + 3 + 3 + 2 + 2 + 2 + 2 + 2 + 2 + 1 = 41번

 

그런데 지금까지 본 n//i의 합인 것 같지만 i = 5인 경우 n//i = 2인데 실제로 3이 나오고 있다

 

즉 i에 대하여 $\left \lceil \frac{n}{i} \right \rceil$이 나오고 있다.

 

그래서 $$\sum_{i = 1}^{n} \left \lceil \frac{n}{i} \right \rceil$$을 구하는 문제

 

n이 $10^{9}$니까 O(N)도 1초안에 될것 같은데 생각했지만 어림도 없네

 

나눗셈이 비용이 많이 들어서 그런가

 

import math

n = int(input())

answer = 0

for i in range(1,n+1):
    
    answer += math.ceil(n/i)

print(answer)

 

 

바로 전에 배운 harmonic lemma에서 $$\sum_{i = 1}^{n} \left \lfloor \frac{n}{i} \right \rfloor$$을 $O(\sqrt{n})$에 구하는 방법을 응용해보자

 

 

https://deepdata.tistory.com/893

1부터 n까지 모든 자연수들 각각의 약수의 누적합을 구하는 방법들(double counting, harmonic lemma, dynami

 

$\left \lceil \frac{n}{i} \right \rceil = x$라고 하자.

 

$$ x-1 < \frac{n}{i} \leq x$$가 성립한다.

 

부등식을 정리하면, $$\frac{n}{x} \leq i < \frac{n}{x-1}$$

 

i = 1이라 하고, x는 어떻게 해야할까? 

 

$\left \lceil \frac{n}{i} \right \rceil = x$니까 math.ceil(n/i) = x로 하면 될 것

 

i가 가지는 하한과 상한을 start, end라고 할때, start,end를 어떻게 구해야할까

 

start = n//x, end = n//(x-1)이라고 하기에는 문제가 있는게 

 

처음에 i = 1일때, x = n이니까 start = 1, end = 1이라서 1 <= i < 1은 부등식이 성립하지 않잖아

 

n/n = 1인데 n/(n-1)은 1.xxxx란 말이지

 

부등식이 성립할려면 어떻게 해야할까

 

1 <= i < 2이면 적절하지

 

그러니까 end = math.ceil(n/(x-1))로 하면 좋을 것 같다

 

그러면 일단 구간의 길이는 end - start인데 다음 i값은 i = 2부터 시작하겠지 

 

n = 18라고 한다면 x = 9이니까 2 <= i < 3

 

그리고 i = 3부터 시작해서 x = 6니까 3 <= i < 4

 

그리고 i = 4부터 시작해서 x = 5인데, 18/5 = 3.6이다

 

그런데 4 <= i로 시작해야하니까 start = math.ceil(n/x)로 하면 적절할 것 같다.

 

그랬을때, 구간의 길이는 end - start로 구할 수 있다.

 

즉 math.ceil(n/i) = x를 만족하는 i의 개수는 end - start개니까...

 

#올림으로 된 조화수열의 합

import math
from sys import stdin

n = int(stdin.readline())

if n == 1:
    
    print(1)

else:

    answer = 0

    i = 1

    x = math.ceil(n/i)
    
    #i가 가지는 범위의 부등식 하한과 상한을 정확히 정의
    start = math.ceil(n/x)
    end = math.ceil(n/(x-1))

    while 1:

        answer += (end-start)*x

        i += (end-start)

        x = math.ceil(n/i)

        if x == 1:

            break

        start = math.ceil(n/x)
        end = math.ceil(n/(x-1))
    
    #반복문을 탈출하면, x = 1인 경우 하나가 빠지게 된다
    print(answer+1)

 

 

근데 이전에 했던 내림 조화수열과는 다르게 x가 0이 되는게 아니고 x가 1이 되면 end의 분모가 0이 되니까 x = 1이 되면

 

반복문을 탈출하도록 하고..

 

x = 1이면 i >= n으로 i = n인 경우만 존재한다.

 

그러니까 반복문을 탈출하면 x = 1이고 i = n인 경우인 $\left \lceil \frac{n}{i} \right \rceil = 1$인 경우 하나가 빠지게 된다

 

그래서 마지막에 answer + 1을 출력

 

그리고 처음부터 n = 1인 경우 x = 1이 되므로, end의 분모가 0이라 에러난다.

 

그래서 n = 1인 경우 예외처리로 처리

 

 

단순히 외워서 할려하니까 시간좀 잡아먹었는데...

 

부등식의 하한과 상한을 정확히 정의하고 머리를 조금 써서 반복문을 빠져나가면 1이 부족하구나 이런 생각을 하니까

 

생각보다 잘 풀리네