[백준][C++] 17425번 문제 "약수의 합" (시간 초과)

출처: 백준

17425번 문제

문제

본문

두 자연수 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)를 출력한다.

예제 입력1

5
1
2
10
70
10000

예제 출력 1

1
4
87
4065
82256014

문제 해석

    이 문제는 17427번 문제와 상당히 유사합니다. 같은 구조이지만 여러개의 테스트 케이스를 받아 출력하는 것이 차이입니다. 따라서 단순히 반복문을 통해 구현한다면 시간 초과로 인해 실패할 것 입니다.

해결방법

    이 문제는 입력으로 들어오는 최댓값까지 미리 연산을 해두는 것이 핵심입니다. 단순히 반복문을 돈다고 한다면 테스트 케이스마다 계산하는 과정이 시간 초과를 유발할 것입니다. 따라서 에라토스테네스의 체를 만드는 것을 응용해 미리 계산을 해둡시다.

Code

#include <iostream>

using namespace std;

long long calculated[1000001];

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

	for (int num = 1; num <= 1000001; num++)
		for(int pos = num; pos <= 1000001; pos += num)
			calculated[pos] += num;

	for (int pos = 2; pos <= 1000001; pos++)
		calculated[pos] += calculated[pos - 1];

	long long	N, T;

	cin >> T;

	while (T)
	{
		cin >> N;
		cout << calculated[N] << "\n";
		T--;
	}
	return (0);
}

Reference