[BOJ/백준][Gold3] 15897 : 잘못 구현한 에라토스네스의 (C++)

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

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

 

[난이도] Gold3
[유형] 수학

[풀이]
6번째 라인을 잘 살펴보면 i가 (1~N) 일때 모든 1+(N-1)/i의 합임을 알 수 있다.
그런데 N범위 10^9이므로 O(N)으로는 시간내에 풀수가 없다.

(N-1)/i 의 값이 똑같은 i들을 한번에 넘어가야한다.

이 과정은 아래 코드로 구현하였다.

    for(long long i=1,cur=N-1;i<N;i+=d,cur=(N-1)/i){
        d = ((N-1)%i)/((N-1)/i)+1;
        ans+=cur*d;
    }

각 변수의 의미는 다음과 같다.
i: (문제의 4번째 라인에서 i와 같은 의미)
cur: 현재 정답에 추가되어야 할 몫의 값 ((N-1)/i의 값)
d: cur과 다른 몫을 가지게 되는 i값이 i+d일때의 d값
(cur의 몫을 가지는 i는 총 d개이다. 그러므로 cur*d만큼을 ans에 더해준 것을 알 수 있다.)

d = ((N-1)%i)/((N-1)/i)+1 <= 이 로직으로 d를 구할 수 있는 이유는 다음과 같다.
현재 몫은 (N-1)/i이고, 나머지는 (N-1)%i이다.
i가 1씩 증가함에 따라 이 나머지는 (N-1)/i씩 줄어들게 된다.
그러므로 i에 ((N-1)%i)/((N-1)/i) 만큼을 더했을 때가 마지막으로 몫이 (N-1)/i인
순간이고, 여기서 i에 1을 더하게 되면 몫이 최초로 (N-1)/i보다 작아지게 된다. => (N-1)/i > (N-1)/(i+d)

글로 설명하기는 어렵기 때문에 각자가 잘 찾을 수 있는 규칙을 찾아보는 것을 추천한다.

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/15897.cpp

 

#include <cstdio>
long long N,ans,d;
int main(){
    scanf("%lld",&N);
    for(long long i=1,cur=N-1;i<N;i+=d,cur=(N-1)/i){
        d = ((N-1)%i)/((N-1)/i)+1;
        ans+=cur*d;
    }
    printf("%lld",ans+N);
}