17425 약수의 합

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초 (추가 시간 없음)	512 MB	4842	1227	919	26.982%

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다.

예제 입력 1

5
1
2
10
70
10000

예제 출력 1

1
4
87
4065
82256014

코드

import java.io.*;
import java.util.Arrays;

public class P_17425 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long[] array = new long[1000001];
        Arrays.fill(array, 1);

        for (int i = 2; i <= 1000000; i++) {
            for (int j = 1; i * j <= 1000000; j++) {
                array[i*j] += i;
            }
            array[i] = array[i - 1] + array[i];
        }

        int n = Integer.parseInt(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        while(n-- > 0) {
            bw.write(array[Integer.parseInt(br.readLine())] + "\n");
        }
        bw.flush();
    }
}

코드 설명

p.17427 약수의 합2처럼 하나씩 구하게 된다면 시간 초과가 발생한다.
따라서, 모두 구해놓고 dp로 푸는 방법을 선택했다.

n의 최댓값이 1,000,000이기 때문에 array의 크기를 1,000,001로 설정한다.
메모리 오버는 기준에 없기 때문에 array를 인덱스 1부터 참조하기 위해서 1,000,001로 설정했다.

에라토스테네스의 체에 기반해서 i를 인수로 갖는 모든 수에 i를 더해주었고, i * j가 최댓값을 넘지만 않으면 되기 때문에 이중 반복문을 i * j <= 1000000로 설정했다.

이럴 경우,

i가 2일 때, 내부 반복문은 n/2
i가 3일 때, 내부 반복문은 n/3
i가 4일 때, 내부 반복문은 n/4
.
.
.
i가 n일 때, 내부 반복문은 n/n

이므로 시간복잡도는 log(n)이 나오게 된다.
즉, 이중 반복문의 시간복잡도는 n * log(n)이므로 최대 600만이 나와 1초가 넘지 않는다.

또, java의 Scanner와 BufferedReader의 경우 BufferedReader가 버퍼 사이즈가 8배 정도 더 크고 Scanner는 6.068초, BufferedReader는 0.934초가 걸리기 때문에 BufferedReader를 사용해서 시간초과를 방지했다.