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

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

17427번: 약수의 합 2

 

문제 해결

• 시간으로 보았을 때 $O(n)$의 시간복잡도를 가져야한다.
• 그러기 위해서는 각각의 약수의 합을 구해서 더하는 방식으로 할 수 없다.(최소 $O(n\sqrt{n})$)
• 1부터 n까지 반복문 $i$을 돌릴 때 n을 $i$로 나누면 n까지 숫자중 $i$를 약수로 갖는 개수가 나온다. 따라서 $i$를 곱해주면 $i$를 약수로 갖는 것들의 개수에 i를 곱하는 것이 된다.
• 따라서 answer = $\sum_{i=1}^{n} [\frac{n}{i}]{i}$가 된다
• 최고자리수가 7자리이므로 int로 부족하고 long long을 써야한다.

CODE

#include<iostream>
using namespace std;

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

.