[#알고리즘/DP/[백준]17425번: 약수의 합(python)]

Question

https://www.acmicpc.net/problem/17425

Code

import sys

input = sys.stdin.readline
MAX = 1000000

# 각 인덱스 숫자의 약수의 합을 담을 배열 (dp 배열)
d = [0] * (MAX + 1)
# 각 인덱스 숫자까지의 약수들의 누적합을 담을 배열
sum = [0] * (MAX + 1)


for i in range(1, MAX + 1) :
    j = 1
    
    while i * j <= MAX :
        # i의 배수에 i 값을 더함.
        # ex) i * 2에 해당하는 값들은 2를 무조건 약수로 가짐.
        d[i * j] += i
        j += 1
    # 누적합 구하기 (이전 숫자의 누적합 + 자신의 약수의 합)    
    sum[i] = sum[i - 1] + d[i]

T = int(input())

for _ in range(T) :
    N = int(input())
    print(sum[N])