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

문제 링크

17427번 - 약수의 합 2

설명

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

접근법

단순하게 1부터 N까지 각 수의 약수를 모두 구한 후 더하면 O(N²) 시간이 걸려 N = 1,000,000일 때 시간 초과가 발생합니다.

대신 약수의 관점에서 생각하면 효율적으로 계산할 수 있습니다.

1부터 N까지 각 수가 어떤 수들의 약수로 포함되는지 세어봅니다.

어떤 수 i는 i, 2i, 3i, …, ki (ki ≤ N)의 약수입니다.

즉, i는 총 ⌊N / i⌋개의 수에서 약수로 등장하므로, i가 g(N)에 기여하는 값은 i × ⌊N / i⌋입니다.

따라서 g(N)을 다음과 같이 계산할 수 있습니다.

g(N) = 1 × ⌊N / 1⌋ + 2 × ⌊N / 2⌋ + 3 × ⌊N / 3⌋ + … + N × ⌊N / N⌋

예를 들어 N = 4일 때:

• 1은 1, 2, 3, 4의 약수 → 1 × 4 = 4
• 2는 2, 4의 약수 → 2 × 2 = 4
• 3은 3의 약수 → 3 × 1 = 3
• 4는 4의 약수 → 4 × 1 = 4

g(4) = 4 + 4 + 3 + 4 = 15

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var ans = 0L;

      for (var i = 1; i <= n; i++)
        ans += (long)i * (n / i);

      Console.WriteLine(ans);
    }
  }
}

C++

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

typedef long long ll;

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

  int n; cin >> n;
  ll ans = 0;

  for (int i = 1; i <= n; i++)
    ans += 1LL * i * (n / i);

  cout << ans << "\n";

  return 0;
}