[백준 / BOJ] C++ 17425 약수의 합

17425번: 약수의 합

 

문제

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

17425번: 약수의 합

 

 

풀이

예전에 모든 수의 약수의 합을 에라토스테네스의 체를 사용해 구하는 법을 9213번 문제를 통해 만들어봤다. [9213 꽤 좋은 수 해설] 링크를 참고해 주길. 어떤 수 A은 A의 배수의 약수다. 범위 내 모든 A의 배수에 A을 더해준다. 그러면 sieve의 A번 인덱스에는 A의 모든 약수의 합을 값으로 가진다. 즉, sieve의 각 인덱스 값은 f(A)이다.

 

우리가 원하는 값은 g(N)이다. g(N)은 1~N의 모든 f(A)의 값의 합이다. 따라서 dp 배열을 만들어주고 점화식을 구하면 dp[i] = dp[i-1] + sieve[i]다. 미리 모두 구한 다음 각 테스트 케이스에 대해 dp[N]을 출력한다.

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  vector<long long> sieve(1000001, 0), dp(1000001, 0);
  for (int i = 1; i <= 1000000; i++)
    for (int j = i; j <= 1000000; j += i)
      sieve[j] += i;
  for (int i = 1; i <= 1000000; i++)
    dp[i] = dp[i - 1] + sieve[i];
  int t, n;
  cin >> t;
  while (t--) {
    cin >> n;
    cout << dp[n] << '\n';
  }
  return 0;
}