#17427번 약수의 합2 (C++)

문제 링크 : www.acmicpc.net/problem/17427

17427번: 약수의 합 2

이 문제는 아래 코드를 보며 이해하면 빠르게 해결할 수 있다.

 

문제 풀이는 다음과 같다.

(1) N=5를 예시로 들어보자.

(2) 1에서 5까지 모든 수들은 1을 약수로 가지고 있다. 때문에 (n/i)*i 를 1로 치환하면 (5/1) * 1, 즉, 5가 5개들어있음을 뜻한다.

(3) 2의 경우, 2에서 한 번, 4에서 한 번 약수를 가지고 있다. 즉, 총 2번을 가지고 있고 합은 4가 된다. 

이를 (n/i)*i에서 2로 치환하면 (5/2)*2, 즉, 2가 2번 있음을 뜻하여 4를 더하게 된다. 

(4) 이러한 원리로 1부터 n까지 모든 약수의 합을 더하게 된다.

#include <iostream>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0;
    long long ans = 0;
    cin >> n;
    for(int i=1; i<=n; i++){
        ans += (n/i)*i;
    }
    cout << ans << "\n";
   return 0;
}