[백준 17425] 약수의 합 (C#, C++) - soo:bak

문제 링크

17425번 - 약수의 합

설명

테스트 케이스 개수 T (T ≤ 100,000)와 각 테스트 케이스마다 자연수 N (1 ≤ N ≤ 1,000,000)이 주어지는 상황에서, f(x)를 x의 모든 약수의 합이라 할 때, g(N) = f(1) + f(2) + … + f(N)의 값을 각각 구하는 문제입니다.

접근법

테스트 케이스가 최대 100,000개이므로 각 쿼리마다 매번 계산하면 시간 초과가 발생합니다.

따라서 미리 1부터 1,000,000까지 모든 값을 전처리한 후 쿼리에 대해 상수 시간에 답해야 합니다.

먼저 1부터 1,000,000까지 각 수의 약수의 합을 구합니다.

이를 효율적으로 계산하기 위해 배수 관점에서 접근합니다.

어떤 수 i는 i, 2i, 3i, …의 약수이므로, i의 배수들을 모두 순회하며 i를 더해줍니다.

1부터 1,000,000까지 모든 i에 대해 이 과정을 반복하면 각 수의 약수의 합을 구할 수 있습니다.

예를 들어 i = 2일 때:

• 2의 약수 합에 2를 더함
• 4의 약수 합에 2를 더함
• 6의 약수 합에 2를 더함
• …

이 방법의 시간 복잡도는 O(N log N)입니다. (조화급수의 합)

다음으로 g(N) = f(1) + f(2) + … + f(N)을 미리 계산합니다.

g(1) = f(1), g(2) = g(1) + f(2), g(3) = g(2) + f(3), … 형태로 누적합을 구합니다.

전처리 완료 후 각 쿼리는 배열에서 값을 읽기만 하면 됩니다.

---

Code

C#

using System;
using System.Text;

namespace Solution {
  class Program {
    const int MAX = 1_000_000;

    static void Main(string[] args) {
      var f = new long[MAX + 1];
      var g = new long[MAX + 1];

      for (var i = 1; i <= MAX; i++) {
        for (var j = i; j <= MAX; j += i)
          f[j] += i;
      }

      for (var i = 1; i <= MAX; i++)
        g[i] = g[i - 1] + f[i];

      var t = int.Parse(Console.ReadLine()!);
      var sb = new StringBuilder();

      for (var i = 0; i < t; i++) {
        var n = int.Parse(Console.ReadLine()!);
        sb.Append(g[n]).Append('\n');
      }

      Console.Write(sb.ToString());
    }
  }
}

C++

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

typedef long long ll;
typedef vector<ll> vll;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  const int MAX = 1'000'000;
  vll f(MAX + 1, 0), g(MAX + 1, 0);

  for (int i = 1; i <= MAX; i++) {
    for (int j = i; j <= MAX; j += i)
      f[j] += i;
  }

  for (int i = 1; i <= MAX; i++)
    g[i] = g[i - 1] + f[i];

  int t; cin >> t;

  while (t--) {
    int n; cin >> n;
    cout << g[n] << "\n";
  }

  return 0;
}