BOJ 1629 곱셈

A의 n제곱을 구하려면 O(n)이 걸릴 것이다. 하지만 A의 n제곱을 O(log n)만에 하는 방법이 있다. 바로 짝수의 제곱을 효율적으로 하는 것이다.

예를 들어 A의 19제곱을 구하고 싶다면
A^19 = A * A^18
A^18 = A^9 * A^9
A^9 = A * A^8
A^8 = A^4 * A^4
....

이런식으로 A의 짝수제곱을 log n만에 구함으로써 A의 n제곱을 O(log n)만에 구할 수 있다.
게시판의 여러 글과 코드를 읽고 알게 되었다.
https://www.acmicpc.net/board/view/4397
https://www.acmicpc.net/board/view/2249 (portableangel님의 코드)

그런데 내 코드가 AC를 못 받았다. 그래서 다른 사람들 코드도 보고 비교해보면서 원인을 찾던 중 재귀함수에서 n==1이면 x를 return하는 것을 n==0이면 1을 return하도록 고치니 AC를 받았다. 또한 n==1이면 x%c를 return했더니 AC를 받았다.

결국 원인은 modular 연산에 있었던 것 같다.
(A * B) mod M = ( (A mod M) * (B mod M) ) mod M 인데,
난 n==1인 경우 mod M을 해주지 않아서 틀린 것 같다. 이 부분에 대해서는 음 아직 좀 헷갈리는 것이 있지만 일단 철저하게 잘 지켜야겠다.