17425. 약수의 합

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

17425번: 약수의 합

 

어떤 수 \( x\) 의 약수의 합을 구하는 함수를 \( f(x)\) 라 하자.

\( x\)보다 작거나 같은 수들의 약수의 합들을 모두 더한 수를 구하는 함수를 \( g(x)\)라 하자.

\( g(x) = \sum_{k=1}^x f(k) \)

 

자연수 \( N\)이 주어졌을 때, \( g(N) \)을 구하는 문제이다.

 

naive한 방법으로 문제를 풀이하면 1부터 1,000,000 까지 모든 \( f(x) \)값을 각각 구한 후, 누적합을 이용해 \( g(x) \)값을 구하는 방법이다.

 

여기서 모든 \( f(x) \)값을 구하는 데에서 \( O(\sqrt{N}) \) 방법이 있다.

\( N \)의 약수 후보인 1부터 \( N \)까지의 수 중에 \( \sqrt{N} \) 까지의 수만 이용해서 약수의 반대편(?)에 있는 수까지 같이 구해 \( f(x) \)를 구하는 방법이다.

for(int i=1;i<=sqrt(N);i++)
{
    if(i * i == N)
    {
        fx[N] += i;
        break;
    }
    else if(N % i == 0)
        fx[N] = i + N/i;
}

 

\( N = a^\alpha + b^\beta + c^\gamma \) 라고 했을 때,

\(N \)의 약수의 합은 다음과 같다.

\( (1+a^1+a^2+\cdots+a^\alpha)(1+b^1+b^2+\cdots+b^\beta)(1+c^1+c^2+\cdots+c^\gamma) \)

 

이를 등비수열의 합 공식으로 표현하면

\( \frac{a^{\alpha+1}-1}{a-1} \) \( \times \)  \( \frac{b^{\beta+1}-1}{b-1} \) \( \times \) \( \frac{c^{\gamma+1}-1}{c-1} \) 가 된다.

 

\( a, b, c \) 는 모두 소수로 구성한다고 하면 소수로 \( f(x) \)를 구할 수 있다.

 

하지만 이 방법으로도 시간안에 들어올 수 없다.

 

 

 

이 문제를 시간안에 해결하려면 에라토스테네스의 체를 응용해야한다.

 

에라토스테네스의 체는 어떤 수 \( a \)가 소수일 때, \(a \)의 배수는 소수가 아니므로 테이블에 소수가 아님을 표시하는 것이 핵심이다. 여기서 \( a\)의 \( k\)배한 수를 \( b\)라고 하면, \(a \)는 \( b\)의 약수이다.

 

이를 이용해서 약수의 합을 저장하는 \( fx\)배열을 만들어 어떤 수 \( i\)의 배수의 약수에 \( i\)가 포함되니 해당 위치에 \( i\)씩 더해 약수를 모두 더한 배열을 만들 수 있다.

이를 누적합하여 \( gx\)배열을 만들면 시간안에 문제를 해결할 수 있다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
#define int long long
 
const int MAX = 1000001;
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    vector<int> fx(MAX, 1);
    for(int i=2;i<MAX;i++)
    {
        for(int j=i;j<MAX;j+=i)
            fx[j] += i;
    }
    vector<int> gx(MAX, 0);
    for(int i=1;i<MAX;i++)
        gx[i] = gx[i-1] + fx[i];
 
    int tc;
    cin >> tc;
    while(tc--)
    {
        int n;
        cin >> n;
        cout << gx[n] << endl;
    }
 
    return 0;
}

이 문제를 해결하는데 있어서 어려웠던 점은 약수를 역으로 생각하여 배수로 생각해 에라토스테네스의 체를 응용한단는 것을 발상하는 부분이었다.