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

https://www.acmicpc.net/problem/17427

17427번: 약수의 합 2

문제

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

해결 방법

위 그림을 살펴보자. N이 10인 경우에 n보다 작은 수들의 약수의 합을 구하는 표이다.

 

이 표를 통해 우리는 i * (n / i)를 n번만큼 더하는 것이 이 문제의 식이라는 것을 알 수 있다.

 

O(n)이 걸리게 된다.

 

입력이 1,000,000이므로 sum은 int 범위인 21억을 초과 할 수있으므로 long long으로 sum을 지정해주면 마무리 된다.

 

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

// 17427. 약수의 합 2
// sum = i * (n / i);
// O(n)

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	long long sum = 0;
	for (int i = 1; i <= n; i++)
		sum += i * (n / i);
	
	cout << sum << '\n';
	return 0;
}