백준 1629 - 곱셈 [C++]

 

---

풀이

 

간단해보이는 문제지만 solved.ac 기준 난이도가 실버 I인만큼 그렇게까지 간단하게 풀리는 문제는 아닙니다.

가장 단순한 방법으로는 A를 B번 곱하고 C로 나머지 연산을 하는 방법이 있으나, B가 최대 2^31 - 1이므로 반복문을 돌릴때 시간초과가 나게 됩니다. 또한, \( A^B \)의 값이 int나 long long 자료형의 범위를 한참 넘어갈 수 있습니다.

 

이를 해결하는데에는 다음과 같은 모듈러 연산의 성질을 이용할 수 있습니다.

$$ \left(A*B\right)\bmod n=\left(A\bmod n*B\bmod n\right)\bmod n $$

이 성질을 이용하면, \( A^B \)를 지수가 2의 거듭제곱인 형태로 분해할 수 있습니다. 예를 들어서, \( 2^{11} \bmod 3 = \left\{ \left( 2^8\bmod 3 * 2^2\bmod 3\right) * 2^1\bmod 3\right\} \)같이 바꿔쓰는게 가능합니다.