1629 곱셈

a의 b 승을 c로 나눈 나머지를 구하는 문제이다.
a,b,c의 범위가 0 ~ 2^31-1 까지라서 O(n)으로 코드를 짜도 TLE(Time Limit Exceeded)가 나와버리고 만다. 간단해 보이지만 생각보다 고생한 문제였다.

내가 처음에 생각한 방법은,
곱셈의 패턴들을 저장해서 패턴이 발견되면 바로 정답을 출력하는 방식이었다.
그러나 c의 범위가 int 범위 이다보니 배열또한 그정도 크기를 줘야해서 무리가 있었고, 크기가 무한정 있었다고해도 패턴의 갯수가 최악의 경우 O(2^31) 이 되버려서 TLE가 나고만다..
그 다음으론 log와 modular의 관계를 이용해서 상수 시간으로 풀어보려고했지만, 도저히 방법이 떠오르지가 않았다.

결국 a^b mod c 에 대해 검색을 하면서 깨닫게 되었는데,
요는 c보다도 b를 빠르게 처리하는것이 관건 이었다.
즉, a의 b승을 최대한 빠르게 구해야 하는것이다.

단, a^b 는 변수로 담아 둘 수 없기 때문에 a=a*a%c 의 연산을 계속 해주어야 한다.
이것은 (a*a*a)%c = (((a%c)*a)%c)*a)%c 와 같다는걸 이용한 것이다.

a의 b승을 빠르게 구하는 방법으로 내가 사용한 알고리즘은,
a^2000 = (a^2)^1000 = (a^4)^500 ... = (a^2000)^1
이렇게 a자체를 증가시키면서 b를 2로 나누는 방법이다.
단순히 a^b를 하게되면 O(b)의 시간복잡도를 갖지만,
위 방법대로하면 O(log2(b))의 시간복잡도를 갖게 되어 문제 해결이 가능하다.
b가 홀수인 경우엔 a를 따로 한번 곱해줘서 짝수로 만들고 2로 나누면 된다.

물론 곱하면서 c로 mod 연산을 계속 해주는것을 잊지말자.

참고 문서

소스