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

출처: 백준

17427번 문제

문제

본문

두 자연수 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)을 구해보자.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 g(N)를 출력한다.

예제 입력 1

1 #### 예제 출력 1
1 #### 예제 입력 2
2 #### 예제 출력 2
4 #### 예제 입력 3
10 #### 예제 출력 3
87 #### 예제 입력 4
70 #### 예제 출력 4
4065 #### 예제 입력 5
1000 #### 예제 출력 5
82256014 ### 문제 해석

    일단 구현해야하는 함수 f( )와 g( )에 대해서 알아봅시다.

    f( ) 함수의 경우 입력으로 들어오는 자연수 N에 대한 약수의 합입니다. 예를 들어 N = 2라면 약수는 1, 2가 됩니다. 따라서 f(2) = 1 + 2 = 3 이 되게 됩니다.

    g( ) 함수의 경우 x보다 작거나 같은 모든 자연수 y의 f(y) 값을 더한 값이라고 합니다. 예를 들어 x = 2라면 f(1) + f(2) = g(2)라는 의미입니다. 따라서 g(2) = 4가 되는 것을 알 수 있습니다.

    하지만 단순하게 자연수 N까지 인덱스를 늘려가며 N을 나누면서 약수를 구하는 방식으로 f( ) 함수와 g( ) 함수를 구현하면 시간 초과로 인해 실패하게 됩니다.

해결방법

    약수와 배수의 성질을 활용한다면 쉽게 해결할 수 있습니다. 예를 들어 1의 배수는 무조건 1을 약수로 갖게되고 2의 배수는 2를 약수로 갖게 되며 3의 배수, 4의 배수 즉 모든 배수는 스스로를 약수로서 갖게 됩니다. 이 성질을 활용하면 해결할 수 있습니다.

N = 6 이라고 가정했을 때 6까지 각각의 약수를 나타내면 다음과 같습니다.

1: 1
2: 1, 2
3: 1, 3
4: 1, 2, 4
5: 1, 5
6: 1, 2, 3, 6

여기서 한가지 패턴을 발견할 수 있습니다. 1은 6개, 2는 3개, 3은 2개, 4, 5, 6은 각 1개씩 존재하는데 이 규칙에서 K * N/K 라는 수식을 도출해낼 수 있습니다. 이를 코딩에 적용하면 됩니다.

Code

#include <iostream>

using namespace std;

long long fg(long long A)
{
	long long index = 1, ret = 0;

	while (A != index)
	{
		ret += index * (A / index);
		index++;
	}
	ret += index * (A / index);

	return (ret);
}

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

	long long	N;

	cin >> N;

	cout << fg(N) << endl;
	return (0);
}

Reference