hiyoko
だいぶ計算できる形になりましたね.
あとはベキ剰余の計算の部分に工夫が必要だとおもわれます.
3^n % 10^m みたいなものを計算するとき,
今回の工夫により, nを1000桁以下におさえたわけですが,
それでも nは100桁などをゆうに超えることが想定されますから, 3^1,3^2,3^3,.., と順々に剰余を求めていく方法は不可能になります.
(そこの部分は基本的なので端折ったという話ならすみません)
以下,破線部以下はネタバレです.
-------------------------------------------------------
計算量を減らす方向だと,
たとえば,カーマイケル関数λに対して,
λ(10^n)=10^(n-1) がいえるわけで,(n≧3)
数の構成法から,常に10^999 の剰余で計算し続ける必要性はないですね.
たとえば, N=3↑↑5 の下5ケタを求めるとき,
N % 10^5 を計算するという話と等価なわけですが,
それは 3↑↑4 % 10^4 の計算結果で決まるわけで,
さらに 3↑↑4 % 10^4 の値は 3↑↑3 % 10^3 で決まり,
3↑↑3 % 10^3 は 3↑↑2 = 27 で決まるということですから,
逆にたどっていくと, 3↑↑3 % 10^3 = 3^27 % 10^3 = 987
3↑↑4 % 10^4 = 3^987 % 10^4 = 9387
3↑↑5 % 10^5 = 3^9387 % 10^5 = 55387
3^n % 10^k の形の計算は binary exponentiation という(ご存知かもしれませんが)よくある方法を用いれば 剰余計算はかなり高速化されます
(具体例でいうなら,3^100 % 10^10 を計算するに際して,
100 = 2^6 + 2^5 + 2^2 より 3^64, 3^32, 3^4 を計算しさえすればいいということから, 3^4を2乗2乗としていき,高速にベキ剰余を求める手法です.
ささいな工夫ですが,とんでもなく計算量を減らしているところに注意です.
実際,これに類する工夫をしないと,今回のもおそらく不可能だと思われます)
以上の2点を組み合わせたものが一応の想定解となります.
実際の計算はまた後で。