http://projecteuler.net/index.php?section=problems&id=337
眠いけど、問題読んだ。今日は久しぶりに夜中まで戦える、と意気込んでみたが、よく分からないなあ。とりあえず、オイラーのφ関数を書いてみるか。
書けた。
S(10)出たけど、S(100)が全然違う。
S(100)出た。でもO(N2)なんだよな。
S(10000)出たけど、あんまり速くなっていない。おかしいな。
そういえば、蟻本にこういう問題の解き方出てたな。
できた。蟻本に書かれていた部分はC++をPythonに翻訳しただけ。でも、メモリがやたらと必要になって大変なことになっていた。たぶん、多倍長整数になってたんだと思うんだけど。
13着か。でも12着から4時間以上かかっていた。12着までは3時間以内だったのに。こんなことあるんだねえ。
日本人トップだったけど、このあと8人中5人が日本人。
結局、どうしてメモリ食っているのか全然分からなかった。
