문제 18
몫의 나머지
양의 정수 $a$, $b$, $n$과 소수 $p$가 주어진다.
$\lfloor b^n/a\rfloor$를 $p$로 나눈 나머지를 구하는 프로그램을 작성하라.
입력
첫 번째 줄에 테스트케이스의 개수를 의미하는 정수 $T$가 주어진다. $(1 \le T \le 500)$
두 번째 줄부터 $T$개의 줄에 걸쳐 네 정수 $a$, $b$, $n$, $p$가 공백으로 구분되어 주어진다. $(1 \le n \le 10^{18}; 1 \le a<b<p \le 10^9+7)$
출력
각 테스트케이스마다 $\lfloor b^n/a\rfloor$를 소수 $p$로 나눈 나머지를 한 줄에 하나씩 출력한다.
예제 입력 1
2 3 5 2 11 2 3 5 7
예제 출력 1
8 2
노트
$\lfloor5^2/3\rfloor\equiv8\pmod{11}$
$\lfloor3^5/2\rfloor\equiv2\pmod{7}$
공식 해설
$b^n$ 전체가 아니라 $ap$로 나눈 나머지만 알아도 몫을 구할 수 있다.
$b^n=kap+r$, $0\le r<ap$로 쓰면
\[
\left\lfloor\frac{b^n}{a}\right\rfloor
=kp+\left\lfloor\frac r a\right\rfloor
\]
이다. $kp$는 $p$로 나누어떨어지고 $0\le\lfloor r/a\rfloor<p$이므로, 구하려는 답은 정확히 $\lfloor r/a\rfloor$이다.
따라서 빠른 거듭제곱으로 $r=b^n\bmod(ap)$를 구한 뒤 정수 나눗셈 $r/a$의 결과를 출력하면 된다. 모듈러 역원은 필요 없다.
거듭제곱에서는 매 곱셈 뒤 $ap$로 나눈 나머지를 남긴다. 두 나머지의 중간 곱은 $(ap-1)^2$까지 커질 수 있으므로, 저장할 나머지의 범위뿐 아니라 이 곱도 정확히 계산할 수 있어야 한다.
테스트케이스당 시간복잡도는 $O(\log n)$, 추가 공간복잡도는 $O(1)$이다.
구현 · 언어별 풀이
C++ 구현
밑·지수·모듈러는 long long으로 두되 곱셈은 (__int128)x * y % mod로 계산한다. mod = a * p도 두 인수가 64비트인 상태에서 구한다. 마지막에는 구한 나머지를 $a$로 정수 나눗셈한 값만 출력한다.
C 구현
mod = a*p와 지수는 long long에 저장한다. 모듈러 곱은 먼저 GNU __int128로 승격하여 계산한 뒤 mod로 나눈다. 마지막에는 정수 나눗셈 r/a의 결과를 출력한다.
Python 구현
pow(b, n, a*p) // a를 사용한다. 세 인수 pow로 모듈러 거듭제곱을 계산하고 //로 정수 나눗셈한다.
Java 구현
a*p 자체는 long에 들어가지만 나머지끼리의 곱은 넘을 수 있다. BigInteger.valueOf(b).modPow(BigInteger.valueOf(n), modulus)로 계산하고 divide(BigInteger.valueOf(a))를 적용한다.
Rust 구현
a*p는 u64 범위지만 모듈러 곱은 u128로 계산한다. 두 피연산자를 곱하기 전에 u128로 변환하고 나머지를 다시 u64로 바꾼다. 마지막에 r/a를 정수 나눗셈한다.
JavaScript 구현
$a$, $b$, $n$, $p$는 모두 BigInt로 읽어 $m=a\cdot p$에서 빠른 거듭제곱을 수행한다. 나머지는 $10^{18}$ 근처, 중간 곱은 그 제곱까지 커질 수 있어 Number로 곱한 뒤 %를 적용하면 정확하지 않다.
let r = 1n % m;
b %= m;
while (n > 0n) {
if (n % 2n === 1n) r = r * b % m;
b = b * b % m;
n /= 2n;
}
const answer = r / a;양수 BigInt의 /는 정수 몫이므로 마지막 나눗셈이 공통 풀이의 바닥 함수와 같다. 출력은 answer.toString()을 사용해 n 접미사가 붙지 않게 한다.