📌 PROBLEM.

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

세 자연수 A, B, C(<= 2147483647)가 있다.
A의 B승을 C로 나눈 나머지를 출력하는 문제이다.

📌 SOLUTION.

1.

단순히 (A ** B) % C로는 문제를 해결할 수 없다.
일반적으로 거듭제곱의 시간복잡도가 O(N)이기 때문이다.
물론 이를 아래와 같이 O(log N)으로 줄일 수는 있다.

import sys


def power(a, b, c):
    if b == 1:
        return a % c

    temp = power(a, b // 2, c)
    return (temp * temp * (a if b & 1 else 1)) % c


A, B, C = map(int, sys.stdin.readline().split())
print(power(A, B, C))

2.

파이썬에서는 power함수와 똑같이 작동하는 함수 pow(base, exp[, mod])를 built-in으로 제공한다.

print(pow(*map(int, input().split())))