백준 17427 - 약수의 합(C++)

문제

두 자연수 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

 

# 풀이 #

1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1
	2	3	2	5	2	7	2	3	2
			4		3		4	9	5
					6		8		10

표를 보면, 예제 3번이 10을 입력하면 87이 나온다 . 그 결과값은 위의 1 ~ 10의 약수를 모두 더한 값이 된다. 

위의 표에서,  1 ~ 10의 약수중 1은 10개, 2의 개수는 5개, 3의 개수는 3개, 4는 2개 .... 

이걸 식으로 정리하면 다음과 같다. 

 

# 정답 #

int main()
{
    int n;
    long long ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int tmp = n/i;
        //cout << "0. tmp : " << tmp << '\n';
        tmp *= i;
        //cout << "1. tmp : " << tmp << '\n';
        ans += tmp;
        //cout << "ans : " << ans << '\n';
    }
    cout << ans << '\n';
    
    return 0;
}