사용자 도구

사이트 도구


ps:problems:boj:1009

분산처리

ps
링크acmicpc.net/…
출처BOJ
문제 번호1009
문제명분산처리
레벨브론즈 3
분류

애드혹

시간복잡도O(1)
사용한 언어Python
제출기록30860KB / 68ms
최고기록52ms
해결날짜2022/01/06

풀이

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

코드

"""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()

토론

댓글을 입력하세요:
M T B Y H
 
ps/problems/boj/1009.txt · 마지막으로 수정됨: 2022/01/13 08:58 저자 teferi