✓

태그:

19. 분할 정복 CLASS 4 ESSENTIAL

\(A^{B}\bmod{C}\)를 빠르게 구하는 문제입니다. 문제의 조건을 보면 A, B, C 모두 int 범위 이내의 큰 자연수입니다. 이걸 반복문으로 A를 B번 곱하면서 C로 나눈 나머지를 구한다는 것은 시간상 절대 불가능합니다(시간복잡도 O(B)). 그래서 조금 더 빠르게 O(log B)의 시간복잡도로 구해보겠습니다. 이 알고리즘은 aⁿ×aⁿ=a²ⁿ을 이용합니다. 이 식을 이용해보면 A²ⁿ=(Aⁿ)², A²ⁿ⁺¹=(Aⁿ)²×A로 나눌 수 있습니다. Aⁿ만 구해도 A²ⁿ과 A²ⁿ⁺¹을 구할 수 있는 것입니다. 이것을 재귀적으로 적용하면 값을 빠르게 구할 수 있을 것입니다. 이제 나머지 조건을 적용하면 식이 A²ⁿ mod C=(Aⁿ mod C)² mod C, A²ⁿ⁺¹ mod C=((Aⁿ mod C)²×A) mod C이 되고, 이를 재귀적으로 적용하여 답을 도출하면 됩니다.

소스 코드

언어	코드	시간
Python 3	코드(Github) / 코드(백준)	2020-04-04 00:12:10

---