파이썬(python) 17425번 약수의 합

문제 링크

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

17425번: 약수의 합

 

처음에는 감을 잡을 수 없었으나 차근차근 패턴을 파악해보았다.

f(6)은 6의 약수의 합 [1, 2, 3, 6], 답 12

f(7)은 7의 약수의 합 [1, 7], 답 8

 

g(6)은 f(1)+f(2)+f(3)+f(4)+f(5)+f(6)을 뜻한다.

1의 약수 1

2의 약수 1 2

3의 약수 1 3

4의 약수 1 2 4

5의 약수 1 5

6의 약수 1 2 3 6

n의 약수를 자세히 보면, 2는 2의 배수인 수(2, 4, 6)에만 포함되어 있다

3은 (3, 6)에만 포함되고, 4는 (4), 5는 (5), 6은 (6)에만 포함되어 있다.

 

약수 1의 개수는 6개, 약수 2의 개수는 3개, 약수 3의 개수는 2개, 약수 4의 개수는 1개, 약수 5의 개수는 1개, 약수 6의 개수는 1개

 

1은 6//1 = 6개

2는 6//2 = 3개

3은 6//3 = 2개

4는 6//4 = 1개
5는 6//5 = 1개

6은 6//6 = 1개

 

이 패턴을 코드화 해본결과는 아래와 같다. 그러나 시간초과 코드

import sys
T = int(sys.stdin.readline())

for _ in range(T):
    a = int(sys.stdin.readline())
    sum_ = 0
    for i in range(1, a+1):
        sum_ += (a//i) * i # 개수X약수
    print(sum_)

0부터 1000000까지의 수

g(0)부터 g(1000000)까지를 리스트로 구해놓고 원하는 수(n)의 g(n)만 찾아 쓰면 시간이 절약

 

import sys

max = 1000000

index_sum = [0]*(max+1)
sum_ = [0]*(max+1) # 누적합, 예,시 [01,3,4,7....]

for i in range(1, max+1): # 1부터 최대까지, 약수 1,2,3...1000000
    a = 1
    while i*a <= max:
        index_sum[i*a] += i
        a += 1
    sum_[i] = sum_[i-1] + index_sum[i]
    
Test_case = int(input())
for _ in range(Test_case):
    a = int(sys.stdin.readline())
    sys.stdout.write(str(sum_[a])+"\n")

많은 블로그를 뒤져보면서 해 본 결과, 다들 python3로는 시간초과가 발생하더라구요. pypy3로 돌려보니 정답처리가 되었네요.