Project Euler 361（2）

http://projecteuler.net/index.php?section=problems&id=361

あれからいろいろ考えて、なんとかA_nの計算量をO(log n)にしたかったのだが、結局断念した。
それでもだいぶ速くなった。

10¹⁸まで 0.06s
10⁵⁰まで 0.65s
10¹⁰⁰まで 0.41s
10²⁰⁰まで3s
10⁴⁰⁰まで23s