[Euler Project 188] 1777의 1885 거듭거듭제곱의 마지막 8자리 구하기

거듭거듭제곱이란 단어는 tetration의 정확한 한국어 번역어를 몰라서 내가 개발한 번역임. 정확한 정의는 검색하여 보기바람. 매우 재미있음.

---

#!/usr/bin/env python

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

def phi(n0):
       ''' euler phi function for n, which consists of only 2 and 5 '''
       n = n0
       pow2 = 0
       while n%2 == 0:
               n/=2
               pow2 +=1
       n = n0
       pow5 = 0
       while n%5 == 0:
               n/=5
               pow5 +=1
       if pow5 == 0:
               if pow2 == 0:
                       return 1
               else:
                       return 2**(pow2-1)
       else:
               if pow2 == 0:
                       return 4*(5**(pow5-1))
               else:
                       return (2**(pow2+1))*(5**(pow5-1))

def powmod(p, pow, n):
       r = 1
       for i in range(pow):
               r *= p
               r %= n
       return r

# crucial to the problem solving
# used recursion. To understand this recursion you should know that
#
#     phi(n)+1
#   p           == p (mod n) when p and n is coprime.
#
# so to find
#
#     m
#   p    mod n
#
#     (m mod phi(n))
#   p                 mod n
#
#, when m is enormous number, it suffices to know first
#
#   m mod phi(n)
#
def nameoji(p, k, n):
       ''' p ^^ k mod n
            p ^^ k is defined
              p ^^ 1 = p
              p ^^ k = p^(p^^(k-1))
        '''
       print(p, k, n)
       if n == 2:
               return p
       pow = (nameoji(p, k-1, phi(n)))
       return powmod(p, pow, n)

print(nameoji(1777, 1855, 10**8))

---