[분할 정복] 빠른 거듭제곱 알고리즘

BOJ 1629 : 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 1629번 제출 맞은 사람 숏코딩 재채점 결과 디버그 채점 현황 강의 곱셈 분류 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 0.5 초 (추가 시간 없음) 128 MB 37835 9690 7134 25.340% 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력 첫째 줄에 A를 B번 곱한 ... www.acmicpc.net BOJ 1629 : 곱셈 딱 봐도, 숫자가 크다. 2^200000000의 값을 구하려면, 2를 20억 번 곱해야 하는데 딱 봐도 시간 초과다. - O(n)는 어림도 없다 분할 정복을 이용한 빠른 거듭제곱을 통해 구...