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

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

 

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

 

출력

각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다.

문제 링크: https://www.acmicpc.net/problem/17425

17425번: 약수의 합

 

    import sys
    input = sys.stdin.readline

    n = int(input())
    MAX = 1000000

    dp = [1] * (MAX+1)
    sum = [0] * (MAX+1)

    for i in range(2, MAX+1):
        j = 1
        while (i*j <= MAX):
            dp[i*j] += i
            j += 1

    for i in range(1, MAX+1):
        sum[i] = sum[i-1] + dp[i]

    for i in range(n):
        x = int(input())
        print(sum[x])

 

(Python 대신 PyPy3으로 제출하셔야 시간초과가 뜨지 않고 정답처리됩니다!!!)

 

dp 리스트는 f(x)라고 보시면 되고, sum이 g(x)라고 보시면 됩니다.while loop에서는 i를 약수로 가지는 모든 숫자에 i를 더해주고 있습니다. 보시면 2, 4, 6, 8, 10 .... 1,000,000에 2를 더했고, 그 다음 iteration에서는3, 6, 9, 12, 15, 18.... 999,999에 3을 더했고,4, 8, 12, ... you get the idea.

 

g(x)를 구해야하기 때문에 sum은 그 전까지의 dp값을 모두 더해서 저장해주어야 합니다.