問題文 問題文の通りに考えると、約数の個数を計算してからKを掛けて足し合わせるイメージになるが演算順序の変更を行うのが肝。問題文の順にやらない。 掛け算は足し算の繰り返しであり、足し算は順序を変えても結果が変わらない。 「条件を満たすものの数を数える」も「条件を満たすなら1、満たさないなら0」の総和を取る処理。 なので「数えた後でK倍」は順番を交換して「条件を満たすならK、の足し合わせ」にできる。
一旦この変換をしておいてから、縦横変換する。横に足したものがKf(K)で、それを足し合わせたものが得たい答え。先に縦に足しても足し算順序の交換なので結果に影響しない。 縦に足したものは等差数列の和なので、ループを回さなくても公式で出せる。 これが解説で紹介されてるやり方 python
def solve(N):
ret = 0
for i in range(1, N + 1):
num = N // i
end = num * i
ret += (i + end) * num // 2
print(ret)
AC 1565 ms https://atcoder.jp/contests/abc172/submissions/14787794
この問題は、もっとオーダーの小さい方法と、大きいけどなんとか通せる方法とがあるそうなので後で探求する。
ところで、この縦に足す方法では、半分から先はどうせ1つしかないのにループを回して一つずつ足してしまう。ここを斜めに足せばループは半分で済む。しかしどうせ斜めに足すなら…
左上までしっかり斜めに足す。そうするとループの回数はルートNのオーダーになる。
python
def solve(N):
ret = 0
i = 2
while True:
step = i // 2
start = (i + 1) // 2 * step
if start > N:
break
end = N // step * step
ret += (start + end) * ((end - start) // step + 1) // 2
i += 1
print(ret)
AC 33 ms https://atcoder.jp/contests/abc172/submissions/14788541 50倍も速くなった