[BOJ/C++] 17425. 약수의 합

https://www.acmicpc.net/problem/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. 앞선 포스트 약수의 합 2번(https://minteul.tistory.com/305)에서 시행한 방법과 동일하다.

[BOJ/C++] 17427. 약수의 합 2

2. 차이점은 testCase가 100,000번 존재한다는 것이고 앞선 문제와 그대로 제출하게 되면 timeout을 보게 된다.

 

3. 그래서 전역변수에 dSum이라는 array를 선언해서 그 값을 담아서 사용하는 방식으로 구현했다.

// Code Plus BasicA
// 0x00. Math
// Written by Rylah
// Written Date : 2022.01.13
// https://minteul.tistory.com/306
// https://www.acmicpc.net/source/37501369

// 17425. 약수의 합
// sum = i * (n / i);
// it's diffrent 17427
// num 1000000 loop 10000
// too many calculation so use global array


#include <bits/stdc++.h>
using namespace std;
long long dSum[1000002];

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	dSum[1] = 1;
	for (int i = 2; i < 1000001; i++)
	{
		for (int j = 1; j * i < 1000001; j++)
		{
			dSum[i * j] += i;
		}
		dSum[i] += (dSum[i - 1] + 1);
	}
	int testCase;
	cin >> testCase;
	while (testCase--)
	{
		int n;
		cin >> n;

		cout << dSum[n] << '\n';
	}
	return 0;
}