Optimization is Freaky Fun( BOJ 17417 )

문제 : https://www.acmicpc.net/problem/17417

17417번: Optimization is Freaky Fun

 

문제 파악하기

입력받은 Q개의 쿼리를 처리하는 문제입니다. 쿼리는 N, S, E를 입력받으며, 구간 [S, E] 사이의 모든 자연수 i를 N으로 나눈 값([N/i])의 합을 구하는 문제입니다. 입력되는 N, S, E 자체가 최대 10¹²이기 때문에 단순한 반복문으로는 해결할 수 없습니다. 또한, 각각의 서브태스크의 조건이 다르기 때문에 시간에 맞춰 문제를 해결하기 위해서는 입력되는 쿼리의 특징에 따라 다른 알고리즘이 필요합니다. 예를 들어 서브태스크 2와 4를 보면 입력되는 모든 N의 값이 동일한 대신, 입력되는 값의 범위가 다른 서브태스크에 비해 크다는 걸 확인할 수 있습니다. 그렇기에 우리는 서브태스크 1, 3, 5와 서브태스크 2, 4를 처리하는 알고리즘을 따로 만들어서 문제를 해결해야 합니다.

 

문제 해결하기

우선, 서브태스크 1, 3, 5를 먼저 해결해봅시다. 해당 서브태스크들은 N의 값이나 Q의 값 중 하나가 비교적 크지 않다는 걸 확인할 수 있습니다. 따라서, 적절한 탐색 알고리즘을 설계하면 2초라는 시간 안에 무난히 해결할 수 있습니다. 그렇다면 모든 [N/i]의 값의 합을 어떻게 빠르게 구할 수 있을까요? 이건 [N/i]의 특징을 살펴보면 쉽게 알 수 있습니다. 우선, N=12이고 [1, 12] 구간의 모든 [N/i]을 살펴봅시다.

[N/i]의 값을 잘 살펴보면 동일한 숫자가 반복되는 구간이 있다는 걸 알 수 있습니다. [7, 12] 구간에서는 1이 반복해서 나타나고 있으며, [5, 6]에서는 2가 반복적으로 나타나고 있습니다. 이처럼 숫자가 반복해서 나타난다면 굳이 모든 숫자를 확인할 필요가 없습니다. 만약 [N/i]의 값이 K라고 하면, K가 나올 수 있는 최대 숫자를 구한 다음 K가 나오는 횟수만큼 곱해서 더해주면  되기 때문입니다. 그럼 만약 [N/i] = K를 만족하는 i의 최댓값은 얼마일까요? i의 최댓값은 바로 N/K입니다. N/K보다 i가 커지면 K의 값이 나올 수 없기 때문입니다. 이렇게 K을 만들 수 있는 최댓값을 구하면 K가 나온 개수만큼 더한 다음에 (N/K+1)번째 숫자를 다시 탐색하면서 원하는 숫자가 되기 전까지 탐색하면 됩니다. 기본적인 소스코드는 다음과 같습니다.

#define lint long long int
 
lint sv(lint n, lint s, lint e) {
    lint cur, nxt, d, sum;
 
    e = min( e, n );
 
    sum = 0; cur = s;
    while(cur <= e) {
        d = n/cur;
        nxt = n/d;
 
        if(nxt > e) {
            sum += (e-cur+1)*d;
 
            break;
        }
        else {
            sum += (nxt-cur+1)*d;
 
            cur = nxt + 1;
        }
    }
 
    return sum;
}

 

이렇게 숫자를 구하면 10¹²의 값까지 1초 안에 계산할 수 있을까요? 확인하기 위해 시간복잡도를 계산해보겠습니다. [N/i]를 했을 때, 서로 다른 숫자는 최대  2*√N개 나올 수 있습니다. 모든 자연수 N은 항상 a*b(a<=b)의 형태로 표현할 수 있으며, 여기서 a가 될 수 있는 가장 큰 수는 √N가 됩니다. 그렇기에 [N/b]의 결괏값인 a는 최대 √N개 나올 수 있습니다. b는 a와 매칭되기 때문에 b 또한 최대 √N개 나올 수 있습니다. 따라서 위 알고리즘의 시간 복잡도는 O(√N)이며, 이는 10¹²의 숫자도 충분히 확인할 수 있는 알고리즘입니다. 따라서, 위의 알고리즘을 사용하면 서브태스크 1, 3, 5는 충분히 통과할 수 있습니다.

 

문제는 서브태스크 2, 4입니다. 사실 서브태스크 2는 쿼리의 개수와 N이 작기 때문에 위의 알고리즘을 사용해도 충분히 통과할 수 있습니다. 하지만 서브태스크 4를 통과하기 위해서는 서브태스크 4의 특성을 고려한 특별한 알고리즘이 필요합니다. 서브태스크 4는 모든 쿼리의 N이 동일합니다. 사실 이런 특수한 경우에는 이분탐색과 누적합을 사용해서 빠르게 구할 수 있습니다. 우선, 입력된 쿼리 중 가장 큰 종료값(E)을 구한 다음, 위의 알고리즘을 사용해서 1부터 E까지의 모든 값의 합을 구합니다. 여기서 다른 점은 모든 숫자의 끝값과 그 때의 누적합을 따로 저장합니다. 예를 들어 N=12일 때, pSum이라는 배열에 다음과 같이 값을 저장할 수 있습니다.

pSum에는 [N/i]=K를 만드는 끝값과 그 때의 누적합이 저장되어 있습니다. 이렇게 배열을 만들면 나머지 쿼리는 금방 처리할 수 있습니다. 만약 [S, E] 구간의 값을 구하고 싶다면 pSum에서 [1, E] 구간의 누적값을 찾은 다음, [1, S-1] 구간의 누적값을 찾아서 빼면 됩니다. 각 구간의 누적값은 이분탐색, 정확하게는 lower bound를 사용해서 특정 구간까지 구한 다음에 나머지는 직접 계산해주면 됩니다. lower bound의 시간복잡도는 O(logN)이기 때문에 서브태스크 2를 처리하는 전체 시간복잡도는 O(QlogN)만큼이며, 이는 10,000개의 쿼리를 처리하기에는 충분한 시간복잡도입니다. 문제를 모두 해결하는 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
#define lint long long int
#define PAIR pair< lint, lint >
using namespace std;
 
struct Inp {
    lint n, s, e;
};
 
int Q, f;
lint N, S, E;
lint maxE, totS, pN;
 
vector< Inp > inp;
vector< PAIR > pSum;
 
lint sv(lint n, lint s, lint e) {
    lint cur, nxt, d, sum;
 
    e = min( e, n );
 
    sum = 0; cur = s;
    while(cur <= e) {
        d = n/cur;
        nxt = n/d;
 
        if(nxt > e) {
            sum += (e-cur+1)*d;
            if(f) pSum.push_back({e, sum});
 
            break;
        }
        else {
            sum += (nxt-cur+1)*d;
            if(f) pSum.push_back({nxt, sum});
 
            cur = nxt + 1;
        }
    }
 
    return sum;
}
 
lint bsearch(lint val) {
    if(val == 0) return 0;
    else if(val >= pN) return totS;
    else {
        PAIR t = make_pair(val, 0);
        vector< PAIR >::iterator its = lower_bound(pSum.begin(), pSum.end(), t);
 
        if((*its).first == val) return (*its).second;
        else {
            its--;
            return (*its).second + (val-(*its).first)*(pN/val);
        }
    }
}
 
int main() {
    // init
    f = 1;
 
    // input
    scanf("%d", &Q);
    for(int i=0;i<Q;i++) {
        scanf("%lld %lld %lld", &N, &S, &E);
        inp.push_back({N, S, E});
 
        if(i>0 and inp[i-1].n != N) f = 0;
        maxE = max( maxE, E );
    }
 
    // Query 1,3,5
    if(f == 0) {
        for (int i=0;i<Q;i++) {
            printf("%lld\n", sv(inp[i].n, inp[i].s, inp[i].e));
        }
    }
 
    // Query 2,4
    else {
        pN = inp[0].n;
        totS = sv(pN, 1, maxE);
 
        for(int i=0;i<Q;i++) {
            if(inp[i].s > inp[i].e) printf("0\n");
            else printf("%lld\n", bsearch(inp[i].e) - bsearch(inp[i].s-1));
        }
    }
}
 
/*
4
17 5 8
17 5 9
17 3 1231231239987
17 3 4
ans
9
10
27
9
 
6
999997 12 999995
999997 2 999992
999997 100000 10000009
999997 211 87762
999997 288997 288997
999997 1 2
ans
10950044
12969907
1928965
5988859
3
1499995
*/
 

 

후기

서브태스크마다 다른 알고리즘을 세우는 문제는 처음이었지만 서브태스크를 유심히 살펴보면 충분히 눈치챌 수 있어 알고리즘을 세우기에는 그리 어렵지 않았습니다. 다만, 쿼리의 입력 중 S > E인 값이 들어올 수 있다는 점을 놓쳐서 나름 오랜 시간이 걸린 문제입니다. 알고리즘에 대해 좀 더 상세한 설명은 아래 참고한 블로그에서 확인해주세요.

 

참고

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

Harmonic-Lemma