[백준]1629 곱셈 #n제곱

1.풀이

 (1) a의 b승을 구하는문제. 진짜 a를 b번 곱하면 당연히 시간초과.

 (2) a^b => (a제곱)^(b//2) 로 계산하는것이 핵심.

   EX) 2^4는 2를 네번곱해야 하지만, 2^4->4^2->16^1로 하면 3번만에 계산가능

 (3) 제곱수가 홀수인 경우는 하나빼서 계산해야 하기 때문에 경우의 수를 나눠준다.

 (4) 제곱수가 1이 될 때 까지 재귀를 반복한다.

​

2. 소스코드

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

def power(a,b):
    #1이면 끝
    if b==1:
        return a%C
    #짝수이면 제곱
    if b%2==0:
        return power(a**2%C,b//2)
    #홀수이면 곱하고 제곱
    else:
        return (a*power(a**2%C,b//2))%C

def main():
    print(power(A,B)%C)

main()