[백준] 17425번 (python 파이썬) 약수의 합

 

문제를 보고 이게 무슨소리인가 했는데

한 자연수A의 모든 약수의 합이 f(A)이고, 어떠한 자연수 Y가 주어지면 그 Y보다 작거나 같은 f(~)를 더한 값이 g(Y)이다.

ex. Y = 10으로 주어진다면 1부터 10까지의 약수의 합f(~)들을 모두 더한 값이 g(Y)이다.

 

특정한 수 n을 약수로 가지는 수는 n의 배수이다.

또한, 1은 모든 수가 약수로 가진다.

이 점을 이용하여 코드를 짜면 된다.

 

문제에서 주어진 자연수의 범위까지 모든 약수의 합을 미리 만들어놓으면 시간을 절약할 수 있다.

728x90

MAX = 1000000
f = [1] * (MAX + 1) 한 자연수x의 모든 약수의 합 f(x) #인덱스는 0부터 시작이니 수로 바로 접근할 수 있게 더 크게 만들어줌
g = [0] * (MAX + 1) 한 자연수y보다 작거나 같은 수의 f(x)들의 합 g(y)
for i in range(2, MAX + 1): # 1은 모든 수가 약수로 가져서 모든 f가 1을 가지도록 만들었기때문에 2부터 시작
    j = 1
    while i * j <= MAX: # MAX까지 i의 배수를 돌음
        f[i * j] += i # i의 배수마다 i를 더해준다.
        j += 1 #다음 배수로 넘어가도록 1을 더해줌

for i in range(1, MAX + 1):
    g[i] = g[i - 1] + f[i]
    
t = int(input())
result = []
for _ in range(t):
    n = int(input())
    result.append(g[n])
print('\n'.join(map(str, result))) #시간단축

pypy3로 제출하지 않으면 시간초과가 난다.

import sys를 사용하면 조금 빨라지겠지만 아직 잘 사용할 줄 몰라서 사용법을 확실히 알게될때 써봐야겠다.