AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典：
AtCoder Beginner Contest 172 D – Sum of Divisors
縦に考えるのが難しければ横に考えてみるとか、そういった感じの問題。個人的には、この回答にあるような表を実際に書いてみないと解けそうにはないかな……。
# 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()
関連
