[수학] 백준 - 약수의 합2

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

17427번: 약수의 합 2

 

-문제해설

무작정 풀면 바로 시간초과뜬다..

풀어서 적어보니 규칙이 있었고 간단하게 구현할 수 있었다.

 

만약 n이 9일경우

f(1) = 1

f(2) = 1 + 2

f(3) = 1 + 3

f(4) = 1 + 2 + 4

f(5) = 1+ 5

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

f(7) = 1 + 7

f(8) = 1 + 2 + 4 + 8

f(9) = 1 + 3 + 9

 

확인해보면 1은 9개, 2는 4개, 3은 3개, 4는 2개, 5는 1개, 6은 1개, 7은 1개, 8은 1개, 9는 1개가 나오는 것을 알 수 있다.

즉, 9/1 = 9, 9/2 = 4, 9/3 = 3, 9/4 = 2, ... , 9/9 = 1임을 알 수 있다.

 

이제 정답인 g( 9 )는 위 f()들을 모두 더해주면 된다.

 

 

-자바

package math;

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

public class BJ17427 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt( br.readLine() );
		long ans = 0;
		
		for( int i=1; i<=n; i++ ) ans += ( n/i ) * i;
		
		System.out.println( ans );
	}
}

 

-파이썬

from sys import stdin
input = stdin.readline
n = int( input() )
ans = 0
for i in range( 1, n+1 ):
    ans += (n//i) * i
print( ans )