테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 분산처리 ======

===== 풀이 =====
  * a^b 를 10으로 나눈 나머지를 구하면 된다.
  * 그냥 a를 곱하고 10으로 나누는 것을 b번 반복하면 O(b)이지만, [[ps:거듭제곱의 빠른 계산]]을 이용하면 O(logb)에 계산 가능하다.
  * 그리고, a, a^2, a^3, ...을 10으로 나눈 나머지는 주기를 갖고 반복되기 때문에, 주기를 구한 뒤에 그것을 이용해서 풀면 O(1)에도 풀수 있다. (구현은 안해봄)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1009. 분산처리".

- Problem link: https://www.acmicpc.net/problem/1009
- Solution link: http://www.teferi.net/ps/problems/boj/1009
"""

import sys


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        m = pow(a, b, 10)
        print('10' if m == 0 else m)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_3 ps:teflib:linear_homogeneous_recurrence}}