백준 1629번 - 곱셈 (Python)

https://www.acmicpc.net/problem/1629밑이 A, 지수가 B인 수를 C로 mod 연산하는 문제이다. input 조건이 굉장히 크기 때문에 그냥 (A**B)%C 이런 식으로 풀면 당연히 틀리고..O(N)으로 풀면 시간 초과가 난다.따라서1. 분할 정복을 사용하여 O(logN)으로 풀어야 하고2. mod 연산의 특성을 알고 있어야 한다.우선 A = 3, B = 13, C = 5 라고 했을 때.. 일반적으로 풀면 3*3*3*...*3*3*3 이런 식으로 3을 13번 곱해야 하지만,1. 분할 정복의 특성을 사용하면 위와 같이 지수를 반으로 나눠준다는 느낌으로,3^13 = 9^6 = 81^3 * 3 = 6561 * 243 으로 지수가 1이 될 때까지 줄여서계산을 하면 무려 3번의 연산..........

원문링크 : 백준 1629번 - 곱셈 (Python)