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

작성일 | In
골드 IV 골드 IV

문제

약수의 합
에라토스테네스의 체를 이용해 약수의 합을 빠르게 구하는 문제입니다.

풀이

약수의 합을 저장한 배열을 먼저 구해봅시다.
$1 \leq i \leq 1,000,000$인 $i$의 배수들에 각각 $i$를 더해줍시다.

1
2
3
4
5
6
7
int size = 1000001;
vector<long long> g(size);
for (int i = 1; i < size; i++) {
    for (int j = 1; i * j < size; j++) {
        g[i*j] += i;
    }
}

답의 자료형으로 long long을 써야 하는 것에 주의합시다.

이제 누적합의 아이디어를 쓰면 $f(1)$부터 $f(i)$까지의 합을 빠르게 구할 수 있습니다.

1
2
3
for (int i = 1; i < size; i++) {
    g[i] += g[i-1];
}

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int size = 1000001;
    vector<long long> g(size);
    for (int i = 1; i < size; i++) {
        for (int j = 1; i * j < size; j++) {
            g[i*j] += i;
        }
    }
    for (int i = 1; i < size; i++) {
        g[i] += g[i-1];
    }

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << g[n] << '\n';
    }
}

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