http://projecteuler.net/index.php?section=problems&id=468
41着。7分。
土曜に風呂に入って考えたら簡単じゃないかと思った。しかし、日曜に組んでみると遅い。なぜ遅いのかわかった。O(N^2/logN)くらいになっているはず。しかし、C++でごり押しができるくらいである。しかし、それを頑張って書いて動かしたところ、失敗していた。
今朝、電車の中でノートに簡単な例の計算書いていたらなんとなく速くなるデータ構造を思いついた。それを歩きながら考えていたら、どうやらO(NlogNloglogN)になるようだ。
今日は比較的早く帰れたので、何日かかけて書けばいいやと思っていたコードが風呂に入る間際に書けた。流して風呂に入ったらPyPyで7分だった。
もう少し速くなる余地はある。素因数分解は遅い実装だし、あと11111112はパッと見でも8と9で割り切れることがわかるのが大きい。しかし、1分は切れそうにない。そもそも、Pythonでクラスを使うと非常に遅いのだ。
