[백준 17427] 약수의 합 2 (C++)

https://www.acmicpc.net/problem/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)를 출력한다.

 

문제 풀이

---

수학 문제.

 

f(1) = 1 = 1

f(2) = 1 + 2 = 3

f(3) = 1 + 3 = 4

f(4) = 1 + 2 + 4 = 7

f(5) = 1 + 5 = 6

f(6) = 1 + 2 + 3 + 6 = 12

...와 같다.

그리고 우리가 구하는 g(N)은 f(1)부터 f(N)까지 더한 값이다.

f를 구할 때 N까지 1은 N번 등장하고, 2는 2의 배수인 모든 수에서 나타나므로 N/2번 등장하고, 3은 3의 배수인 모든 수에서 나타나므로 N/3번 등장한다. 다시 말해 g(N)은 1부터 N까지의 수가 등장하는 횟수를 해당 수만큼 곱해준 값이 된다.

 

아래는 코드.

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	int N;
	long long answer = 0;
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		int counts = N / i;
		answer += (long long) i * counts;
	}
	cout << answer << "\n";
	return 0;
}