[백준] 17427: 약수의 합 2

일단 문제 이해를 못했었다.. N이 2이 2일때 약수를 더했는데 어떻게 4가 나오지...? 이러고 있었다가 10에서 함수를 사용해 대입해보니,

 

g(10) = f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) + f(8) + f(9) + f(10)
g(10) = 1 + 3 + 4 + 7 + 6 + 12 + 8 + 15 + 13 + 18
g(10) = 87

이 도출되었다. 

 

처음에 이렇게 했다가O(n^2) 이라 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 이 조건을 만족하지 못해서

a = int(input())
ans = 0

for i in range(1, a+1):
    for j in range(1, a+1):
        if i % j == 0:
            ans += j

print(ans)

10을 예시로 모든 약수를 적었더니, n / 1 의 나머지 뺀 값이 같아서 아래와 같이 도출하였다.

 

a = int(input())
ans = 0

for i in range(1, a+1):
    ans += (a // i) * i

print(ans)