ABC172-D_SumofDivisorsをpythonで解いた（約数）

問題

• ABC172-D_SumofDivisors

問題概要

Xの正の約数の個数をf(X)とするとき、∑K×f(K)

解法

ポイント

• 整数問題は書き出して規則を捉える
  • 1から始まるときは（ある特定の区間でないときは）特に、一発で答えが出たりする
• 横に集計しても、縦に集計しても同じ
  • -> 横に集計しづらいときは、縦に集計してみる
• 約数の問題は、都度約数を求める場合と、小さい方から予めn倍して格納しておくといい場合がある

コード

• かつっぱさんのコード
  • pypyだと268ms, pythonだと3101ms

n = int(input())

def calc(b, e):
    # 等差数列の和
    cnt = e // b
    return (b + e) * cnt // 2

ans = 0

for i in range(1, n+1):
    ans += calc(i, n//i * i)

print(ans)