[Baekjoon/C++] 17425번 - 약수의 합

[백준] Baekjoon Online Judge

문제로 이동

 

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

 

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

 

출력

각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다.

 

---

예제 입력	예제 출력
5 1 2 10 70 10000	1 4 87 4065 82256014

---

풀이

#include <iostream>
using namespace std;

int f[1000001];
long long g[1000001] = { 0 };

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

	for (int i = 1; i < 1000001; i++) {
		for (int j = i; j < 1000001; j += i) f[j] += i;

		g[i] = g[i - 1] + f[i];
	}

	int T;
	cin >> T;

	for (int i = 0; i < T; i++) {
		int N;
		cin >> N;

		cout << g[N] << '\n';
	}

	return 0;
}

 

	for (int i = 1; i < 1000001; i++) {
		for (int j = i; j < 1000001; j += i) f[j] += i;

		g[i] = g[i - 1] + f[i];
	}

각 숫자들의 약수의 합f와 각 숫자보다 작은 수들의 f의 합g를 미리 구하는 코드이다. 이렇게 미리 f와 g를 구해놓아야 시간 제한에 걸리지 않고 문제를 풀 수 있다.

 

	int T;
	cin >> T;

	for (int i = 0; i < T; i++) {
		int N;
		cin >> N;

		cout << g[N] << '\n';
	}

위에서 구한 g[]를 사용하여 추가적인 계산 없이 바로 답을 출력한다.