문제 36
거듭제곱 2
세 정수 $A$, $B$, $M$이 주어진다.
$A^B$를 $M$으로 나눈 나머지를 출력하라.
입력
첫 번째 줄에 세 정수 $A$, $B$, $M$이 공백으로 구분되어 주어진다. $(1 \le A, M \le 10^9; 0 \le B \le 10^{18})$
출력
$A^B$를 $M$으로 나눈 나머지를 출력한다.
예제 입력 1
2 10 1000
예제 출력 1
24
공식 해설
$B$가 $10^{18}$까지 커질 수 있으므로 $B$번 곱하는 방법 대신 지수의 크기에 대해 로그 시간에 계산하는 방법이 필요하다.
지수를 절반씩 줄이는 빠른 거듭제곱을 사용한다. 지수가 짝수이면 $a^{2k}=(a^2)^k$, 홀수이면 $a^{2k+1}=a(a^2)^k$이므로 한 단계마다 제곱 한 번으로 지수를 절반으로 줄일 수 있다.
누적값 $r=1\bmod M$, 현재 밑 $a=A\bmod M$, 남은 지수 $b=B$로 시작한다. $b$가 홀수이면 $r$에 $a$를 곱한다. 그다음 $a$를 제곱하고 $b$를 $2$로 나눈 몫으로 바꾼다. 모든 곱셈 뒤에는 $M$으로 나눈 나머지를 취한다.
이 과정은 $ra^b\equiv A^B\pmod M$을 유지한다. $b=0$이 되면 $r$만 남으므로 그 값이 답이다. $B=0$이나 $M=1$도 초기값에서 자연스럽게 처리된다.
시간복잡도는 $O(1+\log(B+1))$, 추가 공간복잡도는 $O(1)$이다.
구현 · 언어별 풀이
C++ 구현
밑·누적값·지수를 long long으로 둔다. b & 1이면 누적값에 현재 밑을 곱하고, 밑을 제곱한 뒤 b >>= 1로 지수를 줄인다. 모든 곱셈 뒤 % M을 수행하며, $M\le10^9$이므로 두 나머지의 곱은 long long 범위 안이다.
C 구현
A,B,M과 곱을 long long으로 계산한다. B의 하위 비트가 1일 때 답에 곱하고, 매 단계 A를 제곱한 뒤 B를 오른쪽으로 이동한다. 초기값은 1%M이다.
a, b, m은 앞에서 설명한 정수 자료형으로 두고, 지수의 비트를 한 번씩 처리한다.
long long r = 1 % m;
a %= m;
while (b > 0) {
if (b & 1) r = r * a % m;
a = a * a % m;
b >>= 1;
}Python 구현
pow(A,B,M)이 모듈러 거듭제곱을 직접 계산한다. A**B를 먼저 만들거나 math.pow를 사용하지 않는다. 지수가 $10^{18}$이어도 이진 거듭제곱과 같은 로그 단계 방식으로 처리한다.
answer = pow(a, b, m)Java 구현
long 지수에 비트 검사와 오른쪽 이동을 적용한다. 밑과 답도 long으로 두어 모듈러 곱을 계산하며 BigInteger는 이 문제 범위에서 필요 없다.
a, b, m은 앞에서 설명한 정수 자료형으로 두고, 지수의 비트를 한 번씩 처리한다.
long r = 1 % m;
a %= m;
while (b > 0) {
if ((b & 1) != 0) r = r * a % m;
a = a * a % m;
b >>= 1;
}Rust 구현
u64 지수를 비트 검사하고 오른쪽으로 이동한다. 나머지가 $10^{9}$ 미만이라 곱도 u64로 충분하다. u128은 이 문제의 곱 범위 때문에 반드시 필요한 자료형은 아니다.
a, b, m은 앞에서 설명한 정수 자료형으로 두고, 지수의 비트를 한 번씩 처리한다.
let mut r = 1 % m;
a %= m;
while b > 0 {
if b & 1 != 0 { r = r * a % m; }
a = a * a % m;
b >>= 1;
}JavaScript 구현
$10^{18}$까지의 지수와 최대 $10^{18}$ 근처의 중간 곱을 정확히 처리하려면 입력 토큰을 바로 BigInt로 변환한다. 남은 지수는 b % 2n으로 홀짝을 확인하고 b /= 2n으로 줄인다.
let r = 1n % m;
a %= m;
while (b > 0n) {
if (b % 2n === 1n) r = r * a % m;
a = a * a % m;
b /= 2n;
}
console.log(r.toString());Math.pow나 Number 비트 시프트를 사용하지 않는다. 각 곱 뒤 나머지를 취해 저장값을 작은 범위로 유지한다.