17425번: 약수의 합

문제

자연수 A의 약수의 합을 f(A)라고 합니다. 그리고 자연수 N 이하의 모든 자연수 y에 대하여 f(y)를 더한 값을 g(N)이라고 합니다. 자연수 N이 주어졌을 때, g(N)을 구하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100,000)가 주어집니다. 둘째 줄부터 T개의 줄에 걸쳐 자연수 N (1 ≤ N ≤ 1,000,000)이 주어집니다.
• 출력: 각 테스트 케이스마다 한 줄씩 g(N) 출력합니다.

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

풀이: 에라토스테네스의 체 응용과 누적 합(Prefix Sum)

제한 시간 내에 10만 개의 쿼리를 처리하려면, 입력을 받기 전에 1부터 1,000,000까지의 모든 g(N)을 미리 계산하여 배열에 저장해 두고, 쿼리가 들어올 때마다 배열에서 값을 즉시 찾아 출력하는 O(1) 접근이 필요합니다.

• 약수의 합 배열(f) 구성 (에라토스테네스의 체 원리):
  • N의 최댓값인 1,000,000 크기의 배열 f를 선언합니다.
  • 소수를 구하는 '에라토스테네스의 체'의 원리를 응용하여, 1부터 1,000,000까지의 각 숫자 i에 대해 i의 배수 인덱스마다 i를 더해줍니다.
  • 예를 들어 i=2일 때, 인덱스 2, 4, 6, 8... 위치에 2를 더해줍니다. 이 이중 반복문이 끝나면 f[k]에는 숫자 k의 모든 약수의 합이 저장됩니다.
  • 내부 반복문이 조화급수(Harmonic Series) 형태로 실행되므로 시간 복잡도는 O(Nlog N)이 됩니다.
• 누적 합 배열(g) 구성:
  • 문제에서 요구하는 g(N)은 1부터 N까지의 f(A)의 누적 합입니다.
  • 1,000,000 크기의 배열 g를 선언하고, g[i] = g[i-1] + f[i] 점화식을 통해 누적 합을 미리 계산합니다.
  • 각 누적 합은 10^11에 달할 수 있으므로, 두 배열 모두 long 타입으로 선언하여 오버플로우를 방지합니다.
• O(1) 쿼리 응답:
  • 사전 연산이 모두 끝난 후, 테스트 케이스 T번 동안 입력받는 N에 대해 계산해 둔 g[n]을 바로바로 출력합니다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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));

       // f[i] = i의 약수의 합
       long[] f = new long[1000001];
       // g[i] = 1부터 i까지의 약수의 합의 누적 합 (g(N))
       long[] g = new long[1000001];

       // 1. 에라토스테네스의 체 원리를 응용하여 약수의 합(f) 구하기
       for (int i = 1; i <= 1000000; i++) {
          for (int j = i; j <= 1000000; j += i) {
             f[j] += i;
          }
       }

       // 2. 누적 합(g) 구하기
       for (int i = 1; i <= 1000000; i++) {
          g[i] = g[i - 1] + f[i];
       }

       int t = Integer.parseInt(br.readLine());

       // 3. O(1) 시간 복잡도로 미리 계산된 누적 합 출력
       while (t-- > 0) {
          int n = Integer.parseInt(br.readLine());
          bw.write(g[n] + "\n");
       }

       bw.flush();
    }
}

알고리즘 분류

수학 (Mathematics), 정수론 (Number Theory), 누적 합 (Prefix Sum), 에라토스테네스의 체 응용