[백준] 17427번 - 약수의 합 2 (Silver 2)

문제 링크

백준 17427번 - 약수의 합 2 (Silver 2)

문제 설명

f(a) : a의 약수의 합
g(a) : f(1), …, f(a)의 합
N이 주어졌을 때 g(N)을 계산하는 문제(N < 1000000)

주의점

• overflow에 주의해야한다.
  • $g(N) = O(N^2)$, $g(1000000) \approx 2^{40}$ : int의 범위를 넘는다.

정답 코드 및 설명

import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
        bw.write(""+g(N));
        bw.close();
  }
    
  static long g(int N) {
    long g = 0;
      for(int i = 1; i <= N; i++)
        g += N / i * i;
      return g;
  }
}

• $g(N) = \displaystyle \sum_{i=1}^{N} f(i) = \sum_{i=1}^{N} \sum_{j | i} j$
  • 역으로 생각하기 : $i$는 $\lfloor N / i\rfloor$번씩 더해진다.
  • $g(N) = \displaystyle \sum_{i=1}^{N} i \times \lfloor N / i \rfloor$
• g(N)이 int의 범위를 벗어날 수 있으므로, long으로 구현한다.
• 시간 복잡도 : $O(N)$