Atcoder の記事だとバレないサムネにしてやったわ!
そこのあなた、残念!開いてしまったね?
待った!閉じるんじゃないよ!諦めて読んでいきなさい。
土曜は麻雀に興じていたので Atcoder をサボってしまった。
しかし!
その後、問題を見て勉強をした。
Atcoder にストイックな男と呼んでくれ!
問題:
正の整数 x について、x の約数の個数を f(x) とする。
正の整数Nが与えられたとき、
を求めよ。
つまり、
1×(1の約数の個数)+2×(2の約数の個数)+3×(3の約数の個数)+・・・・
・・・・+N×(Nの約数の個数)
を求めろ、ということだ。
答えはこうらしい。
n = int(input())
s = 0
for i in range(1, n+1):
q = n//i
s += q*(q*i+i) // 2
print(s)
これ何なのかわかる??
わかる人は、以下もう読まなくても大丈夫だ。
僕はさっぱり意味がわからなかったので、こいつを読み解いて考え方を探るのは諦めることにして、自力で思い付く方法から地道に考えてみることにした。
さて、普通に考えるのならば、約数の個数を求めるべきだろう。
約数の個数の求め方は、素因数分解して、
とするのが一般的だが、
素因数分解して、指数にそれぞれ1を足して、掛け合わせて。
それを 1~N までの数に対して1つずつ行って。
如何にも時間が掛かる、この方針では間に合いそうもない。
そこで、こんなアルゴリズムがあるそうだ。
n = int(input())
table = [0] * n
for i in range(1, n+1):
for j in range(i, n+1, i):
table[j-1] += 1
print(table)
何をしているかと言うと、
1~n までのリストを用意しておき、
1の倍数、2の倍数、3の倍数・・・と順番にカウントしていく。
これで 1~n までの約数の個数を持ったリストが完成する。
こいつを使えば、元の問題も、これで終わりだ。
n = int(input())
table = [0] * (n+1)
for i in range(1, n+1):
for j in range(i, n+1, i):
table[j] += 1
ans = 0
for i, j in enumerate(table):
ans += i*j
print(ans)
PyPy を使えば通るが Python だと時間オーバーになる。
もう少し工夫して Python で通るようにしたい。
今の状態は、それぞれ集計してから、Nを掛けて、それから和を求めている。
集計するのを止めて、直接的に和を求めた方が早いだろう。
N = int(input())
ans = 0
for i in range(1, N+1):
for j in range(i, N+1, i):
ans += j
print(ans)
PyPy の実行時間はかなり早くなるが Python がほとんど変わらない。
もっと工夫しなければ。
ここで、
最初に載せた答えがどこから来てるのかわかったぞ!
なるほどぉぉぉ。
等差数列なので和の公式で求められる。
こっちの公式で出そう。
項数を q = N // i とすると、 ※ // は余りのある割り算の商を求める。
初項 i 、項数 q 、末項 q × i なので。
q × ( i + q×i ) ÷ 2
という訳で。
N = int(input())
ans= 0
for i in range(1, N+1):
q = N//i
ans += q*(q*i+i) // 2
print(ans)
Pytnon でも通る、PyPy 早っ。
という訳だったんですね~。
これ我ながらよく結論まで辿り着けたと思っている、天才かもしらん。
約数の個数を列挙するアルゴリズムから出発して、徐々に今回の問題を解くことに特化したアルゴリズムに洗練されていく過程が面白かったので記事にしてみた。
僕が、あ!!!!わかった!!!!ってなった瞬間の感動が伝わっただろうか。
少しでも伝わっていると嬉しい。
Atcoder のキャッチコピーだが、コンテストに参加せず、しかも答えを最初に見てしまってから考えても、わかった!!が体験できるのだ。非常に良く出来たパズルだ。
さあ、みんなも Let's Atcoder !!