백준 17425 약수의 합

n도 백만에 테케도 십만이라 시간초과를 고려해서 풀었으나 시간초과가 떴다...

첫 번째 풀이

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        ll sum = 0;
        for (int i = 1; i <= n; ++i) {
            sum += (n/i) * i;
        }
        cout << sum << '\n';
    }
}

시간 내에 통과하기에는 어림도 없었다.

두 번째 풀이

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    vector<int> dp(1000001);
    for (int i = 1; i <= 1000000; ++i) {
        ll sum = 0;
        for (int j = 1; j*j <= i; ++j) {
            if (i % j == 0) {
                sum += j;
                if (j*j != i) sum += i/j;
            }
        }
        dp[i] = sum;
    }
    vector<ll> pSum(1000001);
    pSum[1] = 1;
    for (int i = 2; i <= 1000000; ++i) {
        pSum[i] = pSum[i-1] + dp[i];
    }
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << pSum[n] << '\n';
    }
}

전처리 과정에서 O(n√n) 시간복잡도를 가져 아슬아슬하게 통과하지 않을까 했는데 시간초과가 떴다.
계속 고민하다가 a의 배수는 a를 약수로 가진다는 성질을 이용하면 O(n)에 가까운 속도로 전처리를 할 수 있다는 것을 떠올렸고 수정 후 제출했다.

마지막 풀이

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    vector<int> dp(1000001);
    for (int i = 1; i <= 1000000; ++i) {
        for (int j = 1; j * i <= 1000000; ++j) {
            dp[i*j] += i;
        }
    }
    vector<ll> pSum(1000001);
    pSum[1] = 1;
    for (int i = 2; i <= 1000000; ++i) {
        pSum[i] = pSum[i-1] + dp[i];
    }
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << pSum[n] << '\n';
    }
}

드디어 통과했다.
약수의 성질에 대해 배울 수 있는 좋은 문제였다.