Project Euler 188

プロジェクトオイラー
http://projecteuler.net/index.php

Q188.
a↑↑bを次のように再帰的に定義する。
a↑↑(k+1) = a(a↑↑k)
このとき、1777↑↑1855の下8桁を求めよ。

オイラーの定理より、

1777φ(108) ≡ 1(mod 108)

φ(108) = 4×107より、17774×107 ≡ 1(mod 108)。だから、17772×107 ≡ 1(mod 108)となって、1777108 ≡ 1(mod 108)となる可能性がある。実際計算してみると、そうなることを確認できる。ここまでわかればあとは簡単で、

bk = a↑↑k % 108
a = 1777

とおくと、

bk+1 = a(a↑↑k) % 108 = a(a↑↑k % 108) % 108 = abk % 108

となる。



def mul(a, b, n):
return a * b % n

def pow(m, e, n):
if e == 1:
return m

p = pow(m, e / 2, n)
if e & 1:
return mul(m, mul(p, p, n), n)
else:
return mul(p, p, n)

N = 10 ** 8
a = 1777
b = 1855
print pow(a, N / 5, N)
c = a
for k in range(2, b + 1):
c = pow(a, c, N)
print c