문제 37
모듈로 곱셈의 역원
정수 $A$가 주어진다. $998\,244\,353$은 소수이다.
$A \times X$를 $998\,244\,353$으로 나눈 나머지가 $1$이 되도록 하는 정수 $X$를 출력하라.
입력
첫 번째 줄에 정수 $A$가 주어진다. $(1 \le A < 998\,244\,353)$
출력
$A$의 모듈로 곱셈 역원을 출력한다.
예제 입력 1
1
예제 출력 1
1
예제 입력 2
2
예제 출력 2
499122177
공식 해설
$p=998\,244\,353$은 소수이고 $1\le A<p$이므로 $A$와 $p$는 서로소이다. 페르마의 소정리에 따라
\[
A^{p-1}\equiv1\pmod p
\]
이다.
따라서 $X=A^{p-2}\bmod p$로 두면 $AX\equiv1\pmod p$가 되어 원하는 역원이다. 지수가 크므로 $p-2$번 곱하지 않고 빠른 거듭제곱으로 계산한다. 곱할 때마다 $p$로 나눈 나머지를 남기되, 중간 곱은 $(p-1)^2$까지 커질 수 있음을 고려한다.
시간복잡도는 $O(\log p)$, 추가 공간복잡도는 $O(1)$이다.
구현 · 언어별 풀이
C++ 구현
빠른 거듭제곱으로 $A^{p-2}\bmod p$를 계산한다. 밑과 누적값을 long long으로 저장하면 나머지를 취하기 전의 곱도 안전하다. 최종 나머지를 그대로 출력한다.
C 구현
모듈러 거듭제곱 함수로 A의 p-2제곱을 구한다. p=998244353의 나머지끼리 곱은 long long 범위다. 나눗셈이나 float 역수로 대체하지 않는다.
Python 구현
pow(A,998244353-2,998244353)를 사용한다. Python의 세 인수 pow로 페르마 소정리에 따른 역원을 계산하며 실수 1/A를 구하지 않는다.
Java 구현
long으로 이진 모듈러 거듭제곱을 계산한다. 지수는 p-2이며 매번 곱한 뒤 나머지를 취한다. 입력 A가 0이 아니므로 역원이 존재한다.
Rust 구현
u64로 p-2제곱을 이진 거듭제곱한다. 매 단계 나머지를 취하면 곱도 u64 안이다. 정수 A를 f64로 바꾸어 역수를 구할 필요는 없다.
JavaScript 구현
$p=998\,244\,353$ 자체는 Number로 정확하지만 두 나머지의 곱은 안전 정수 범위를 넘는다. 998244353n을 모듈러로 두고 BigInt 빠른 거듭제곱으로 $A^{p-2}\bmod p$를 계산한다.
남은 지수가 홀수일 때 누적값에 밑을 곱하고, 밑을 제곱한 뒤 지수를 정수 몫으로 반씩 줄인다. 각각 % p를 적용한다. 역원을 1 / a 같은 실수로 구하거나 전체 거듭제곱을 먼저 만들지 않는다. 답은 문자열로 출력한다.