[백준(python)] 17425번: 약수의 합

17425번: 약수의 합

문제

두 자연수 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)를 출력한다.

풀이

max = 1000000

M = [0 for i in range(max+1)] #누적합 g(x)를 담는 메모
m = [0 for i in range(max+1)] #해당 값의 약수의 합 f(x)를 담는 메모

for i in range(1,max+1):
    j = 1
    while i * j <= max: # i*j 값이 최대값이 넘지 않을 때까지
        m[i*j] += i
        j += 1
    M[i] = M[i-1] + m[i]

n = int(input())
divList = list()
for i in range(n):
    a = int(input())
    divList.append(a)
for i in divList:
    print(M[i])

설명

M[3] -> 1의 약수의합 + 2의 약수의합 + 3의 약수의 합 (통칭 누적합)
m[3] -> 오직 3의 약수의 합을 담고있음

while i * j <= max:

i*j가 인덱스 역할을 해줄테니 최댓값 max를 넘으면 안된다

m[i*j] += i

만약 i가 3이라고 가정하면
3*j에 해당하는 값들 즉, 3의 배수들은 무조건 3을 약수로 갖고있음.
따라서 m[3*j]에 해당하는 값들(3의 배수들)에 전부 3을 더해줘야함

M[i] = M[i-1] + m[i]

해당 m[i]의 값까지 더한 누적합을 M[i]에 넣어준다.
i가 1부터 2, 3, 4, 5, ... 로 커져가면서
1의 배수에 해당하는 수에 다 1을 더해주고
2의 배수에 해당하는 수들에 전부 다 2를 더해주고
3에 해당하는 수들에 전부 3을 더해주고...
즉, i에 해당하는 수의 배수들에 i의 값을 다 더해준거임.
i가 더이상 더해질 일은 없어. 앞으로는 i보다 더 큰 숫자들을 더해주겠지. 따라서 for문이 i를 지난 후에는 M[i]의 누적합을 구할 수 있는 거야