[백준][C++] 17425: 약수의 합

문제

17425번: 약수의 합

풀이

수학, 정수론, 누적 합 문제이다.

 

for (int i = 1; i <= 1000000; ++i)
{
    for (int j = 1; i * j <= 1000000; ++j)
    {
        cache[i * j] += i;
    }
}

• 위의 코드를 사용하면 O(N * log(N))의 시간복잡도로 약수들의 합을 구할 수 있다. 각 i에 대한 배수들을 활용하여 i * j의 약수인 i를 더하는 방식이다.
• 우리가 필요한 것은 g(x)이다. g(x) = (g - 1) + f(x)이므로 누적 합을 이용하여 구할 수 있다.

 

코드

#include <iostream>

using namespace std;

long long cache[1000001];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;

    // 먼저 약수들의 합을 구해야 한다.
    // 약수들의 합을 O(N * log(N))의 시간복잡도로 구한다.
    for (int i = 1; i <= 1000000; ++i)
    {
        for (int j = 1; i * j <= 1000000; ++j)
        {
            cache[i * j] += i;
        }
    }
    // 구해야 하는 것은 g(x)이므로 g(x) = g(x - 1) + f(x)이다. 
    // 누적 합으로 g(x)를 구한다.
    for (int i = 2; i <= 1000000; ++i)
    {
        cache[i] += cache[i - 1];
    }

    while (T--)
    {
        int N;
        cin >> N;

        // g(N)을 출력한다.
        cout << cache[N] << '\n';
    }

    return 0;
}