백준 17425번: 약수의 합 (골드 4)

제출 코드

T = int(input())

tc_list = [] #테스트 케이스를 저장할 리스트
for _ in range(T):
    N = int(input())
    tc_list.append(N)

#가장 큰 테스트 케이스에 대해서 약수의 합 계산
#약수의 합을 위한 계산이 한번만 수행되도 됨
N = max(tc_list)
div_sum = [0]*(N+1)
for i in range(1, N+1):
    for j in range(i, N+1, i):
        div_sum[j] += i

#누적 합 저장
g_sum = [0]*(N+1)
for i in range(1, N+1):
    g_sum[i] = g_sum[i-1]+div_sum[i]

#각 테스트 케이스에 대해 출력    
for t in tc_list:
    print(g_sum[t])

 

코멘트

시간을 줄이기 위해 가장 큰 테스트케이스에서만 계산을 해두면 나머지 경우의 연산은 수행하지 않아도 된다.

 

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

 

약수의 합 성공

 

골드 4 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초 (추가 시간 없음)	512 MB	21378	5242	3902	25.290%

 

문제

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

예제 입력 1  

5
1
2
10
70
10000

예제 출력 1  

1
4
87
4065
82256014