[BOJ] 1629번: 곱셈

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

pow(A, B) % C 를 정직하게 A를 B번 곱하는 방식으로 구하게 될 경우 시간복잡도는 $O(B)$가 되고 시간 내에 품을 장담할 수 없습니다.

그러나 재귀를 활용해서 pow(A, B)를 구하기 위해 pow(A, B/2)를 이용한다면 시간복잡도를 $O(log B)$로 떨굴 수 있습니다. 거의 25문제 가까이 한 번의 제출만에 맞았는데 이 문제에서 연산 중간에 long long 범위를 벗어날 수 있음을 망각하는 바람에 여러번 틀리게 되었습니다. 항상 조심해야합니다.

https://github.com/encrypted-def/BOJ/blob/master/1629.cpp