[Python]분할정복 백준 1629

   문제

   https://www.acmicpc.net/problem/1629

제곱의 계산을 분할정복을 통해 해결하는 문제이다.

#a=nc+r이라고 생각햇을때
#a^2=(nc)^2+2(nc)r+r^2
#a^2를 c로 나눈것의 나머지는 r^2%c
def squared(a,b):
    if b==0:
        return 1
    elif b==1:
        return a
    elif b%2==1:
        return squared(a,b-1)*a
    half=squared(a,b//2)
    half%=c
    return half**2%c
 
 
a,b,c=map(int,input().split())
print(squared(a,b)%c)