プロジェクトオイラー
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 % ndef 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