[백준/수학] 17427 약수의 합2(Python, 파이썬)

www.acmicpc.net/problem/17427  

17427번: 약수의 합 2

 

 

- f(A) = A의 약수의 합

- g(N) = f(1) + f(2) + ... + f(N)

- N이 주어졌을 때, g(N)을 구하는 문제

 

 

우선, 약수를 구하는 방법에는 두가지가 있다.

 

1. 자연수 N이 주어졌을 때, 1부터 N까지 나누어가면서 나머지가 0인 값을 구하는 방법

2. 자연수 N이 주어졌을 때, 약수는 서로 대칭구조를 이루고 있으므로 1부터 $\sqrt{A}$까지의 약수를 구하는 방법

 

그러나 이 문제에서는 시간 제한이 1초 이므로 시간 복잡도가 각각 $O(n^2)$ , $O(n\sqrt(n))$인 위의 방법을 사용할 수 없다.

 

그렇다면,

3의 배수를 생각해보자. 3의 배수는 3, 6, 9, ... 이다. 즉, 3의 배수는 3을 약수로 갖는다. 

또한 4의 배수는 4를 항상 약수로 갖는다.

또한 5의 배수는 5를 항상 약수로 갖는다.

.

.

.

N의 배수는 N을 항상 약수로 갖는다.

 

그러므로 N이하의 자연수 중에서 i를 약수로 갖는 개수는 $N/i$개 이다.

이런 원리를 이용해서 약수의 갯수를 구할 수 있다. 이제 그 갯수에 약수만 곱하여 더하면 문제의 답을 구할 수 있다.

 

$$g(N)=1\times N/1 + 2\times N/2 + \mathrm{...} + N\times N/N$$

 

이 경우의 시간 복잡도는 $O(n)$이다.

 

 

* 예를 들어가며 생각하면 더 쉽게 생각해볼 수 있다! 

import sys
input=sys.stdin.readline

n = int(input())

sum_ = 0
for i in range(1, n+1):
	# i의 배수의 개수 = i를 약수로 갖는 수
    sum_ += (n//i)*i

print(sum_)