Y箱

95番です。友愛数の列をみつける問題です。

 2月に解いていたのに、なぜかここにエントリを作っていませんでした。 そんなわけで、どんな風に解いたのかうろ覚えなので、コードを読んで解説してみます。


友愛数を見つけるためには約数の和を求める必要があります。約数関数はσ(n)で表わされて、公式もあったりして、以前の問題ではそれを使ったりしたのですが、素因数分解が必要で時間がかかります。
今回は、趣向を変えて、以前勉強会のときに考えた、エラトステネスの篩のロジックを使って約数の総和の一覧を求めて使うことにしました。

エラトステネスの篩は、数の一覧から、「ある数の倍数になっているものを削除」することで素数を見つけますが、YがXの倍数ということはXはYの約数であるということを使って「ある数の倍数の場所にその数字を足す」ということで総和を求めます。

一覧ができてしまえば、あとはたどって行くだけです。
ただ、A->B->C->D->E->(C)のように途中からループしたり、さらに、M->N->D->E->C->(D)のようあるループに横から突入するパターンも考えられるので、それを考慮した探索にしてあります。

時間は1分をいくらか超えてしまっていますが、許容範囲でしょう。