Last Two [Fast Exponentiation Algorithm]

https://codefights.com/challenge/ZtjccseoDxaSEkujv

Author

SourMongoose

3000

Given two integers n and k, find the last two digits of nk.

Example:
For n = 14 and k = 4, the output should be
lastTwo(n, k) = "16"

144 = 38416, so the answer is "16".

• [input] integer n

  10 ≤ n < 109

• [input] integer k

  1 ≤ k < 109

• [output] string

  The last two digits of nk.

n의 k승의 마지막 두자리를 리턴하면 된다.

간만에 쉬운 문제다! 라고 쓲쓱 써서 제출하니까 시간 초과..

인생에 쉬운게 어딨겠습니까만은..

<고수들은 보기만 해도 구토를 유발하게된다는 O(n) 복잡도>

아마 이렇게 일일이 곱해보는 방법 말고 다른 방법이 있는 듯 하다.

짱돌을 조금 굴려보니 어차피 계속 곱하다 보면 끝 두자리 숫자는 반복된다는 것을 알아냈다.

그럼 이 반복되는 수열을 찾아서 length가 m인 배열로 배열화시키고

k%m 의 인덱스를 찾으면 바로 되지 않을까?

하지만 이렇게 말로 풀면서도 코드가 길이가 너무 길어지는게 느껴진다.

다른 상위권 사람들을 보니 대부분 150자 언저리에서 마무리를 짓는다.

다른 방법을 찾아보자.

해답은 Fast Exponentiation Algorithm

이걸 쓴다면 log(n)의 시간 복잡도로 해결이 가능하다는데..?

참조

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation