문제 35
거듭제곱 1
세 정수 $A$, $B$, $M$이 주어진다.
$A^B$를 $M$으로 나눈 나머지를 출력하라.
입력
첫 번째 줄에 세 정수 $A$, $B$, $M$이 공백으로 구분되어 주어진다. $(1 \le A, M \le 10^9; 0 \le B \le 100\,000)$
출력
$A^B$를 $M$으로 나눈 나머지를 출력한다.
예제 입력 1
2 10 1000
예제 출력 1
24
공식 해설
$B$가 최대 $100\,000$이므로 $A$를 $B$번 곱하는 방법으로 충분하다. 누적값을 $1\bmod M$으로 초기화하고 다음 갱신을 $B$번 반복한다.
\[
r\leftarrow (rA)\bmod M.
\]
$i$번 반복한 뒤의 값은 $A^i\bmod M$이다. 곱셈 중간에 나머지를 취해도 최종 나머지는 바뀌지 않으므로 마지막 값이 답이다.
초기값부터 나머지를 취하면 $B=0$일 때도 올바르며, $M=1$이면 $0$이 된다. 나머지를 취하기 전의 곱은 $10^{18}$ 미만이므로 중간 계산에서도 이 범위를 고려한다.
시간복잡도는 $O(B+1)$, 추가 공간복잡도는 $O(1)$이다.
구현 · 언어별 풀이
C++ 구현
누적값과 밑, 모듈러를 long long으로 두고 r = r * A % M을 반복한다. 정수의 나머지가 필요하므로 실수 거듭제곱 함수 pow는 사용하지 않는다. 초기값은 1 % M이다.
C 구현
r=1%M부터 B번 r=r*A%M을 반복하면 제한 내에서 충분하다. r과 A를 long long으로 곱한다. B=0과 M=1일 때도 초기값이 올바른 답이다.
Python 구현
공통 풀이대로 r=1%M에서 B번 모듈러 곱을 반복한다. B가 최대 100000이므로 이 방식으로 충분하다. A**B를 먼저 만든 뒤 나머지를 구하거나 math.pow로 실수를 만들지 않는다.
Java 구현
r과 A를 long으로 두고 r=1%M부터 반복한다. Math.pow는 double 연산이므로 정확한 모듈러 계산에 사용하지 않는다. 각 곱은 $10^{18}$보다 작아 long에 들어간다.
Rust 구현
u64로 r=1%M을 초기화하고 B번 곱한 뒤 나머지를 구한다. M이 $10^{9}$ 이하라 나머지끼리의 곱은 u64에 들어간다. 부동소수 powf는 필요 없다.
JavaScript 구현
밑과 모듈러가 $10^9$까지이므로 두 나머지의 곱은 $10^{18}$ 근처가 된다. Number 곱셈 뒤 %만 적용하면 하위 자리 정보가 이미 사라질 수 있어 밑·나머지·모듈러에는 BigInt를 사용한다. 반복 횟수 $B\le100\,000$은 Number여도 된다.
r = 1n % m에서 시작해 $B$번 r = r * a % m을 수행한다. 지수가 $0$이거나 $m=1$인 경우도 초기값으로 처리된다. a ** BigInt(b)로 거대한 정수를 먼저 만들지 않는다.