AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

ABC172 D - Sum of Divisors

問題原文

atcoder.jp

解法

普通に解けなかったので解説をガン見した。

キーとなる性質は「ある数  K が 何かで割れると、答えが  +K される」ということ。
で、例えば  5, 10, 15... は当然どれも 5で割れるわけなんですが、これは答えに  +5, +10,  +15 ... されるのと同じ。
つまり、等差数列の和の公式で一発で出せますね。。。

これを  1 〜 N についてやればOK 。 O(N) で通る。

実装

N = int(input())

ans = 0
for x in range(1, N + 1):
    n = N // x
    ans += n * (2 * x + (n - 1) * x) // 2

print(ans)

感想

敗因は  K × は切りわけにくそうと決め付けちゃったことかなぁ。。。 視点を切り替え切れませんでした。
こういうのかなり弱点そう。