17425.py

17427에서 g(N)을 구할 때, O(N)만에 가능한 것을 알게되었다.

그런데 이 문제에서는 테스트 케이스가 100000개 주어진다.
테스트 케이스가 주어질 때는 변하지 않는 값은 케이스마다 계산해서 출력하지 말고, 전체 경우를 모두 계산한 후, 출력을 모아서 해주는 것이 좋다.

//pypy3
import sys
MAX = 1000001

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

for i in range(1, MAX):
    g[i] = g[i - 1] + f[i]

answer = []
n = int(sys.stdin.readline().rstrip())
for i in range(n):
    m = int(sys.stdin.readline().rstrip())
    answer.append(g[m])

print('\n'.join(map(str, answer)) + '\n')

f[i]를 더 빨리 구하기 위해서 배수를 사용했다.
(a를 약수로 갖는 수는 a의 배수)
예를들어 2를 약수로 갖는 수는 2, 4, 6, ... 이므로
f[2], f[4]. f[6], ... 에 2를 더해준다.

그리고 g[i]는 f의 누적합이므로 g[i] = g[i - 1] + f[i]로 구할 수 있다.