[BOJ] 백준 17425번 약수의 합 (Java)

#17425 약수의 합

난이도 : 골드 5 

유형 : 정수론 / 누적 합 

17425번: 약수의 합

▸ 문제

두 자연수 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)를 출력한다.

 

문제 풀이  

각 약수의 합을 구한다음 N의 약수의 합을 f(N)이라고 했을 때 i:1~N까지의 f(i)의 누적합을 구해주면 된다. 먼저 약수를 구해보자. 최댓값이 100만이기 때문에 100만까지 속해있는 수들의 모든 배수들을 고려해주면된다. 다음과 같은 식을 통해 약수를 구할 수 있다.

• i의 배수들을 구하는 식이다. 따라서, i=2, j=1~500,000까지 2를 약수로 가지는 수(i*j)들에 2를 저장한다. 
• 예를 들어, i*j = 4인 경우는 (2*2), (4*1) 두 가지 경우가 있다. 그래서 4의 약수는 2와 4임을 알 수 있다.

long[] dp = new long[MAX];
Arrays.fill(dp, 1);
for(int i=2; i<MAX; i++) {
	// i*j의 약수 i 구하기 
// i*j = 4의 약수는 2*2, 4*1 -> 2와 4
	for(int j=1; i*j<MAX; j++) {
		dp[i*j] += i;
	}
}

 

이젠 이렇게 구한 약수들의 합들의 누적합을 구하여 저장해주면 된다.

for(int i=1; i<MAX; i++) {
	cSum[i] = cSum[i-1] + dp[i];
}

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static final int MAX = 1_000_001;
	public static void main(String[] args) throws IOException{
		long[] cSum = getDivisorSum();
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int t = Integer.parseInt(br.readLine());
		while(t-- >0) {
			sb.append(cSum[Integer.parseInt(br.readLine())]+"\n");
		}
		System.out.println(sb.toString());
	}
	
	private static long[] getDivisorSum() {
		long[] dp = new long[MAX];
		Arrays.fill(dp, 1);
		for(int i=2; i<MAX; i++) {
			// i*j의 약수 i 구하기 
			// i*j = 4의 약수는 2*2, 4*1 -> 2와 4
			for(int j=1; i*j<MAX; j++) {
				dp[i*j] += i;
			}
		}
		
		long[] cSum = new long[MAX];
		// 4 124 => 7
		for(int i=1; i<MAX; i++) {
			cSum[i] = cSum[i-1] + dp[i];
		}
		return cSum;
	}
}