(2024-11-07) 4 문제 : 백준 - 17425 (약수의 합)

 

일종의 DP문제이다. 이준 반복문을 통해 약수의 합을 미리 구할 수 있다.

숫자 하나를 골라서 해당 숫자의 배수가 되는 숫자에 모두 해당 숫자를 더해준다.

 

예를 들어, 현재 숫자가 2라면 2, 4, 6, 8, 10 .... 등 2의 배수에 모두 2를 더해주는 것이다. 현재 숫자가 3이라면 3, 6, 9, 12...등 3의 배수에 모두 3을 더해주면 된다.

 

1~1000000까지 모든 숫자를 기준으로 배수가 되는 숫자에 자신을 더해주면 된다. 이중 반복문이 수행횟수가 엄청 많을 줄 알았는데 계산해보니 1400만번 정도로 시간초과가 날 정도는 아니었다.

 

#include <iostream>
#include <map>
#include <cmath>
#include <vector>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    std::vector<long long> DevisorSum(1000001);
    DevisorSum[1] = 0;

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

    for (int i = 2; i <= 1000000; i++)
    {
        DevisorSum[i] += DevisorSum[i - 1];
    }

    int NumCase = 0;
    std::cin >> NumCase;

    for (int Case = 0; Case < NumCase; Case++)
    {
        int TargetNum = 0;
        std::cin >> TargetNum;

        std::cout << DevisorSum[TargetNum] << "\n";
    }

    return 0;
}