백준 17425: 약수의 합(JAVA)

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

17425번: 약수의 합

이 문제는 이전 문제의 심화버전인 것 같다. 이전 약수의 합 문제 + 여러 개의 테스트 케이스

이전 17427번 문제를 풀었던 코드를 응용했다. n이 1부터 1000000까지 f(n)과 g(n)을 구한다.

여기서 g(n) = g(n-1) + f(n)이라는 것을 알면 코드를 쉽게 짤 수 있다.

 

T번 만큼 N을 입력받아 각 g(N) 값을 출력해주는데 여기서 입출력에 드는 시간을 단축시키기 위해 BufferedReader와 Stringbuilder를 사용하였다. 

(이전에는 Scanner로 문제를 풀어 제출했는데 시간초과가 떴음)

g(n)을 저장하는 변수는 long타입으로 선언해야 함을 주의하자.

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

public class Main {
	static long[] g = new long[1000001];
	public static void main(String[] args) throws NumberFormatException, IOException{
		int T, N;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int[] fn = new int[1000001];
		
		for(int i=1; i<1000001; i++) {
			for(int j=1; i*j<1000001; j++)
				fn[i*j]+=i;
			g[i] = g[i-1] + fn[i];
		}
		
		T = Integer.parseInt(br.readLine());
		
		for(int i=0; i<T; i++) {
			N = Integer.parseInt(br.readLine());
			sb.append(g[N]+"\n");
		}
		System.out.println(sb);
		
	}
}