AtCoder Beginner Contest 172 [ D - Sum of Divisors ] https://atcoder.jp/contests/abc172/tasks/abc172_d

abc172_d.py

'''
[問題]
https://atcoder.jp/contests/abc172/tasks/abc172_d

[参考]
https://youtu.be/v8ppNGf49Nk?t=6627
　snukeさん解説放送。
　ここで解説されている方法に基づいて実装。
'''

import sys

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

N = int(input())

# f[i] にiの約数の数を保存する配列を作成。どの数も1の倍数ではあるので、1で初期化
f = [1] * (N + 1)
f[0] = 0    # 0の倍数は0にしとく。使ってないけど

# iの倍数を1ずつカウントアップしていく。この計算量はO(logN)くらい。調和級数とのこと。
for i in range(2, (N + 1)):
    for j in range(i, (N + 1), i):
        f[j] += 1

# k * f[k] を k=1〜N までの範囲で全合計する
ans = 0
for k in range(1, (N + 1)):
    ans += k * f[k]

print(ans)