[수학] 백준 - 약수의 합

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

17425번: 약수의 합

 

-문제해설

전에 풀었던 약수의 합2와 비슷하지만 테스트케이스 개수로 인해서 약수의 합2와 같은 풀이로 풀면 시간초과가 된다.

따라서 미리 f()와 g()를 만들고 테스트케이스의 n값에 따라 답을 출력하는 식으로 풀어야 한다.

 

먼저 f()를 만드는 방법은 모든 약수에는 1을 포함하고 있으므로 Arrays.fill() 메서드로 f() 배열에 1을 채워준다.

 

그리고 만약 약수 2가 있을 경우 2의 배수들(4, 6, 8, 10...)에는 모두 2를 약수로 포함하고 있기 때문에

2를 모두 더해준다.

f(2) += 2

f(4) += 2

f(6) += 2

 

만약 약수 3일경우 3의 배수들에 3을 모두 더해준다.

f(3) += 3

f(6) += 3

f(9) += 3

 

 

이렇게 f()를 모두 만들었으면 이제 g()를 모두 만들어준다.

g()를 만드는 식은 다음과 같다.

 

g( i ) = g( i-1 ) + f( i )

 

왜 이런 식이 만들어지냐면 아래를 살펴보면 된다.

g( 1 ) = f( 1 ) = 1

g( 2 ) = f( 1 ) + f( 2 ) = g( 1 ) + f( 2 ) 

g( 3 ) = f( 1 ) + f( 2 ) + f( 3 ) = g( 2 ) + f( 3 )

g( 4 ) = f( 1 ) + f( 2 ) + f( 3 ) + f( 4 ) = g( 3 ) + f( 4 )

 

이제 소스코드를 보면 이해가 될 것이다.

 

-자바

package math;

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

public class BJ17425 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder sb = new StringBuilder();
		long f[] = new long[ 1_000_001 ];
		long g[] = new long[ 1_000_001 ];
		
		//1은 모든 수의 약수이므로 추가
		Arrays.fill( f, 1 );
		
		//먼저 f()를 모두 만들어준다.
		//만약 i가 2일 경우 2의 배수들에는 모두 2가 약수가 되므로 2를 더해준다.
		//만약 i가 3일 경우 3의 배수들에는 모두 3이 약수이므로 3으 더한다.
		//j 반복문의 범위는 i*j까지이다. 
		//i가 2이고 j가 500,000이면 i*j는 1,000,000이기 때문이다.
		for( int i=2; i<f.length; i++ ) {
			for( int j=1; i*j<f.length; j++ ) {
				f[ i*j ] += i;
			}
		}
		
		//이제 g()를 만들어준다.
		//식은 다음과 같다. g(i) = g(i-1) + f(i)
		for( int i=1; i<g.length; i++ ) {
			g[i] = g[i-1] + f[i];
		}
		
		//각 테스트케이스에 따라 g()값을 출력해준다.
		int t = Integer.parseInt( br.readLine() );
		while( t --> 0 ) {
			int n = Integer.parseInt( br.readLine() );
			sb.append( g[n] ).append( "\n" );
		}
		System.out.println( sb );
	}
}

 

 

-파이썬

from sys import stdin
input = stdin.readline
f = [1] * 1000001
g = [0] * 1000001

for i in range( 2, len(f) ):
    j = 1
    while i*j < len(f):
        f[ i*j ] += i
        j += 1

for i in range( 1, len(g) ):
    g[i] = g[i-1] + f[i]

t = int( input() )
for _ in range( t ):
    n = int( input() )
    print( g[n] )