[BOJ] 1629번 곱셈

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

이항 계수 3을 풀다가 관련되어서 풀게 된 문제이다.
한 수의 n승을 분할정복을 통해 빠르게 얻을 수 있고, 여기에 모듈로 연산 분배법칙을 함께 이용하면 풀이되는 문제이다.

모듈로 연산 분배법칙은 +,-,x에서 가능하고 /는 특수한 상황에서 가능하다.

def pow_plus_modulo(num, n, m):  # (num^n) % m 구하기
    if n == 1:
        return num % m

    if n % 2 == 0:  # n이 짝수
        return (pow_plus_modulo(num, n // 2, m)**2) % m
    else:
        return ((pow_plus_modulo(num, (n - 1) // 2, m)**2) * (num % m)) % m


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