AtCoder Beginner Contest 172 D – Sum of Divisors をPython3で解く

# AtCoder Beginner Contest 172 D - Sum of Divisors
# https://atcoder.jp/contests/abc172/tasks/abc172_d
# tag: 整数 約数 考察

# 制約がかなり厳しく、O(N^2) はおろか、O(N logN)でも
# 間に合いそうにない。

# 公式解説を見るとなんだか騙された気になってしまうが、
# 具体的に考えてみると、以下の通り。

# 試しに、N=6 の場合について考えてみる
# n を 1 ～ 6 の範囲で動かしながら、1 ～ 6 で割り切れるか
# どうかを確認していくことになる。

# 1 で割り切れるのは 1, 2, 3, 4, 5, 6
# 2 で割り切れるのは 2, 4, 6
# ...といったのをまとめたのが下の表で、この表内の数字の合計が
# 求めたいもの、ということになる。

# n -  1  2  3  4  5  6
# ---------------------
# 1 -  1  2  3  4  5  6
# 2 -     2     4     6
# 3 -        3        6
# 4 -           4      
# 5 -              5
# 6 -                 6

# これを問題文の通り各列ごと（縦方向）に見て合計を求めるのは難しいが、
# （f.e. 4 の約数は 1, 2, 4 の 3 個になるので、4 を 3 回足す）
# 各行ごと（横方向）に見ると、簡単に求めることができる。

# すなわち、初期値 i, 最大値 <= N, 差分が i の等差数列の合計を、
# 1 <= i <= N の範囲で求めるということになる。

def main():
    N = int(input())
    result = 0

    for i in range(1, N+1):
        # 上記で言うところの等差数列の個数
        num = N // i

        # 等差数列の最大値
        mx = i * num

        # 等差数列の合計を、答えに足す
        result += (i + mx) * num // 2
    
    print(result)

main()