#1457 정확해

정확해라는 문제는 약수들의 합을 구하는 문제입니다.

난이도는 Gold I 문제이긴 하지만, 이게 수학적인 이해를 하지 못 하면 조금 어렵습니다.

그래서인지 정답자가 제가 푼 시점에서는 40명에 그칩니다.

 

약수의 개수를 구하는 문제는 꽤 어렵습니다.

 

\[ \sigma_0(n) = n( \lbrace x | n~ mod~ x = 0 \rbrace ) \]

 

으로 약수를 구하는 식을 사용한다면, \(\sqrt{n}\)에 해당하는 만큼 약수가 되는 개수를 구하던지, 소인수 분해를 해주어야 합니다.

 

그런데 만약 1 부터 n까지의 약수들의 개수의 합을 구하라는 문제라면 어떨까요?

 

\[ S(n) = \sum_{k=1}^{n} \sigma_0(k) \]

 

하나의 수의 약수의 개수를 구하는 것도 어려운데, 일정 숫자 범위의 약수의 개수를 구하라는 것은 더 어렵겠죠.

 

하지만 역으로 생각해보면, 1의 배수가 몇개이고, 2의 배수가 몇개이고, ..., n의 배수가 몇개인지 센다고 하면요.  그러면 훨씬 간단한 문제로 귀결될겁니다.

 

\[ S(n) = \sum_{k=1}^{n} \sigma_0(k) = \sum_{k=1}^{n} \lfloor \frac{n}{k} \rfloor \]

 

이렇게 하면 일정범위의 약수의 개수를 쉽게 구할 수 있습니다.

 

s = 0;
for(int k = 1; k <= n; k++)
    s += n/k;

위와 같이 작성하면 n이하의 수들에 대한 약수 개수의 합을 구할 수 있습니다.  알고리즘 효율은 \(O(n)\)이 되겠죠.

 

n = 5라고 한다면, 1부터 5까지 나누는 수는 5, 2, 1, 1, 1 이 됩니다.  즉, 5/2 보다 큰 수에 대해서는 1이 되는 것이죠.  이를 이용하면 우리는 절반만 하면 됩니다.

 

n = 12라고 한다면, 1부터 12까지 나누는 수는 12, 6, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1 가 될겁니다.  1이 6번, 2가 2번 나타납니다.  일단 1로 나누는 수를 제거하더라도 실제 나올 수 있는 숫자들은 제한적입니다.

 

이를 위해서 다음과 같이 작성해볼 수 있습니다.

s = 0;
for(int i = 1, k = 0; i <= n; i = k+1)
{
    k = n/(n/i);        //. n/i는 i로 나눌수 있는 배수의 개수이고, 해당 개수와 같은 나눔 수의 최대값
    s += (n/i) * (k-i+1);
}

이 형태로 하면 우리는 실제 반복해야 하는 횟수를 줄일 수 있습니다.

 

이렇게 범위의 약수의 개수를 구하고, 그리고 \(x^N\)을 위한 부분을 처리하면 됩니다.  이 부분은 \(O(n^{1/N})\)이 될테니 앞에 약수의 개수의 합을 구하는 것보다는 더 낫습니다.

 

그래서 구현한 소스는 다음과 같습니다.

소스는 참고용으로만 봐주세요.

 

//----------------------------------------------------------
//    baekjoon #1457 - Is Accurate
//        - by Aubrey Choi
//        - created at 2022-08-15
//----------------------------------------------------------
#include <cstdio>

int pow(int a, int n)
{
    int p = 1;
    for(int i = 0 ; i < n; i++) p *= a;
    return p;
}

int main()
{
    int a, b, n;
    scanf("%d%d%d", &a, &b, &n);
    unsigned sum = 0;
    for(int i = 1, k = 1; i <= a+b; i=k+1)
    {
        k = (a+b)/((a+b)/i);
        sum += (a+b)/i * (k-i+1);
    }
    for(int i = 1, k = 1; i < a; i=k+1)
    {
        k = (a-1)/((a-1)/i);
        sum -= (a-1)/i * (k-i+1);
    }
    sum -= (b+1)*2 - (a==1);
    for(int i = 2; ; i++)
    {
        int pw = pow(i, n);
        if(pw > a+b) break;
        int m = (pw < a)?a-1:pw-1;
        sum -= (a+b)/pw - m/pw;
    }
    printf("%d\n", sum);
}