문제

문제 링크 : https://www.acmicpc.net/problem/1629

풀이

'분할 정복을 이용한 거듭제곱'이라는 방법을 사용하여 푸는 문제이다. 단순하게 그냥 풀면 시간 초과가 뜬다.

자세한 설명은 백준 11444번 풀이 글에 적어두었다.

import sys
input = sys.stdin.readline

a,b,c = map(int,input().split())

def mul(a,b,c):
    if b == 1:
        return a % c
    temp = mul(a,b//2,c)
    if b % 2 == 0:
        return (temp * temp) % c
    else:
        return (temp * temp * a) % c

print(mul(a,b,c))