nで剰余をとる % n でO(n^2)時間がかかっていると思われ。
>>355 の場合はどうでしょう。>>367

>>349 にあるように %n 以外でもO((log n)^19)と桁数の19乗で時間が
増えていくので
3^19 : 4^19 = 1 : 236.5
4^19 : 5^19 = 1 : 69.38
それに桁数が小さいときは18次以下の項も大きく利いてきて
桁数の増加に伴い大きく時間を伸ばしている可能性があります。>>369