백준 1629(곱셈) - python

접근

큰수의 제곱문제. 연산 횟수를 줄이는 문제인데 12^4 을 (12^2)^2 이런식으로 연산 횟수를 줄일 생각을 했다.

또 중요한 부분이 수를 줄이는 것인데 A**B의 결과에 C를 나누는 것이나. A%C **B나 결과가 같게 나온다는 것을

이용해야겠다는 생각을 했다.

예시

12*12 = 144

144%7 = 4

 

(12%7) * (12%7) = 25

25 % 7 = 4

 

나의 코드

import sys
input = sys.stdin.readline

A,B,C = map(int,input().split())

count = 1
cnt = 0
while B >= 5:
    if B%2 == 1:
        count *= A

    A = (A**2) %C
    B = B//2

print(((A**B)*count)%C)