[백준] C++ 알고리즘 17425번 - 약수의 합

문제

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

17425번: 약수의 합

소스코드

#include <iostream>
#include <bits/stdc++.h>
using namespace std; 
int MAX = 1000000;
long long dp[1000001];
long long s[1000001];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    fill_n(dp, MAX + 1, 1);
    for (int i = 2; i <= MAX; i++) {
        for (int j = 1; i*j <= MAX; j++) {
             
                dp[i*j] += i;
             
        }
    }
    for (int i = 1; i <= MAX; i++) {
        s[i] = s[i - 1] + dp[i];
    }
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        cout << s[n]<<"\n";
    }
}

풀이

이전의 약수의 합2문제와 문제는 똑같다. 하지만 이 문제의 키는 약수의 합2 문제와 같지만, 시간초과를 조심해야 한다.

우선 매번 테스트케이스마다 약수를 구해서 더하고하는 건 너무 비효율적이므로, dp를 생각해볼 수 있다.

그렇다, 미리 먼저 약수들의 합을 구해놓고 테스트케이스에서는 그냥 계산된 값을 출력만 하는 것이다.

 

우선 n=ab 일때, a b는 n의 약수이고 n은 a b의 배수 이다라는 성질을 이용한다.