[코테] 백준 - 약수의 합2(17427)

문제

• 자연수 N 제공
• 자연수 A의 약수의 합을 f(A)로 정의
• N보다 작거나 같은 모든 자연수들의 f(A)의 합을 g(N)이라 할때, g(N)을 구할 것

코드

#include <iostream>
#include <numeric>
#include <queue>
#include <vector>

using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n=0;
    cin>>n;
    vector<long long> SumN(n+1,0);
    for (int i=1;i<=n;i++)
    {
        for (int j=i;j<=n;j+=i)
        {
            SumN[j]+=i;
        }
    }
    long long answer=accumulate(SumN.begin(),SumN.end(),0LL);
    cout<<answer;
    return 0;
}

풀이

• 에라토스테네스의 체 응용
• SumN: n+1개의 원소를 가진 배열 선언 ㅡ> 해당 수의 약수의 합(f(x) 저장용)
• i의 값을 1~n 까지 차례대로 값을 증가
• j의 값을 i~(n보다 작거나 같은 i의 배수) 까지 증가
• j의 값을 인덱스로 활용하여 SumN의 값에 누적
  ㅡ> 반복문이 끝나면 모든 약수가 누적된 형태

 

---

참고자료

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

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전