약수의 합 - 백준 17425 [Python]

 

 

문제해석)

문제에서 주의할 점은, 약수의 합2 문제와는 다르게 테스트 케이스의 수가 주어져 시간복잡도를 잘 고려해야한다는 점이다.

 

따라서 변하지 않는 값일 경우, 매번 테스트 케이스마다 구하는 것이 아니라 한번에 미리 구해둔 다음 그 값을 이용하는 방식으로 문제를 해결한다. 

 

문제 해결을 위해

• N보다 작거나 같은 모든 자연수는 N의 약수와 약수가 아닌 수로 나눌 수 있다.
• 약수의 개수는 약수가 아닌 수의 개수보다 매우 작다.
• 불필요한 연산을 줄이기 위해서 배수를 이용해 약수를 구할 수 있다.

이 방법을 이용한다면, 시간 복잡도는 O(NlgN)이 된다.

 

정답)

MAX = 1000000;
d = [1]*(MAX+1)
s = [0]*(MAX+1)

for i in range(2, MAX+1):
    j=1
    while i*j <= MAX:
        d[i*j] += i
        j += 1
        
for i in range(1, MAX+1):
    s[i] = s[i-1] + d[i]
  
t = int(input())
ans = []

for _ in range(t):
    n = int(input())
    ans.append(s[n])

print('\n'.join(map(str,ans))+'\n')