[C/C++] 백준 #2247 실질적 약수(수학)

#2247 문제는 주어진 범위안의 1과 자기자신을 제외한 약수들의 합을 계산하는 문제입니다.

 

문제의 링크입니다.

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

2247번: 실질적 약수

 

수학에서 약수와 배수는 밀접한 상관관계가 있습니다.  \(2 \times 5 = 10 \)이란 식에서 2와 5는 10의 약수이기도 하지만, 10은 2의 배수이고, 10은 5의 배수이기도 합니다.

 

 

이 문제는 위의 원리를 잘 이해하는데에서 출발합니다.

 

문제는 주어진 N에 대해서 1부터 N까지 1과 자기자신을 제외한 약수들의 총 합을 구하라는 문제입니다.

 

일일이 하나씩 해보면, 1과 소수는 조건에 맞는(실질적) 약수는 없습니다.  4, 6, 8, 9, 10이 각각 약수를 가지고 있습니다.  그래서 2, 2, 3, 2, 4, 3, 2, 5 를 다 더해야 합니다.  그 합이 23이 됩니다.

 

이렇게 생각하면 문제의 답을 구할 때, 약수들의 합을 구하면 간단하다고 생각할 수 있습니다.  하지만 큰 수의 약수를 모두 계산하는데에는 \(O(N)\)의 시간복잡도를 가지고 있고, 이것을 N개에 대해서 다 하려면, \(O(N^2)\)의 시간을 필요로 합니다.  물론 약수를 모두 계산할 때, 제곱근을 기준으로 왼쪽과 오른쪽이 쌍을 이룬다는 원리를 이용해도 \(O(N \sqrt{N})\)의 시간을 필요로 합니다.  N의 범위가 몇만도 아니모 20억까지인 점을 고려하면, \(O(N)\)도 힘듭니다.

 

그래서 배수들을 이용해서 하면 됩니다.  배수를 이용하면, 2의 배수의 개수, 3의 배수의 개수, 4의 배수의 개수 등을 계산하면 약수들의 합을 계산할 수 있습니다.  1부터 N까지 2의 배수의 개수는 \(\lfloor N/2 \rfloor\)가 됩니다.  이를 수식으로 하면, 다음과 같이 표현할 수 있습니다.

 

\[ CSOD(n) = \sum_{k=2}^{n-1} ( \lfloor N/k \rfloor - 1 ) k \]

 

자 위의 식을 이용해서 1부터 10까지의 실질적 약수의 합을 구하면, 2x4 + 3x2 + 4x1 + 5x1 + ... = 23 이 됩니다.  6부터 9까지는 실질적으로 0이 나오기 때문에 필요가 없습니다.  훨씬 간단해졌고, 이렇게 계산하면 \(O(N)\) 알고리즘이 됩니다.  이래도 시간초과는 명확합니다.

 

\[ CSOD(n) = \sum_{k=2}^{\lfloor n/2 \rfloor} ( \lfloor N/k \rfloor - 1 ) k \]

 

1부터 10까지의 숫자 중 잘 보시면, 약수의 개수가 같은 것들이 나옵니다.  바로 4와 5입니다.  이것들을 고려해서 제작을 하시면 됩니다.  1부터 10까지의 숫자 중에서는 4의 배수는 2개입니다.  그러면 10을 2로 나누어 몫을 구하면, 같은 개수가 나오는 최대 정수인 5를 구할 수 있습니다.  즉, 4와 5는 같은 개수를 가지고 있기 때문에, 우리는 이를 이용해서 풀면, 2x4 + 3x2 + (4+5)x1 = 23 을 얻을 수 있습니다.

 

이것을 프로그램한 소스를 저는 이렇게 작성했습니다.

//------------------------------------------------
//    baekjoon #2247 - Actual Divisor
//        - by Aubrey Choi
//        - created at 2019-05-31
//------------------------------------------------
#include <stdio.h>

int solve(int n)
{
    long long sum = 0;
    int i = 2;
    while(i <= n/2)
    {
        int k = n/i;
        int b = n/k;
        long long c = (long long)(k-1)*(b-i+1)*(i+b)/2;
        sum = (sum+c)%1000000;
        i = b+1;
    }
    return (int)sum;
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", solve(n));
}

 

하지만 이것보다 두배정도 더 빠르게 계산할 수 있는 방법도 있습니다.  건너띄기를 하는 것이 아니고, \( 2 \times 5 = 10 \) 과 같이 2를 얻으면, 5를 자동으로 얻는 방법을 사용하는 것입니다.  그러면 건너띄기를 하는 것보다 더 빠르게 처리할 수 있습니다.

 

//--------------------------------------
//    baekjoon #2247 - Actual Divisor
//        - by Aubrey Choi
//        - created at 2019-05-31
//--------------------------------------
#include <stdio.h>
#include <math.h>

int main()
{
    int n, sqrtn, i; long long sum = 0;
    scanf("%d", &n);
    sqrtn = (int)(sqrt(n)+0.0000001);
    for(i = 2; i <= sqrtn; i++)
    {
        int k = n / i;
        sum += i * (k - i + 1) + (long long)(k - i) * (k + i + 1) / 2;
        sum %= 1000000;
    }
    printf("%lld\n", sum);
}