7090 : 모듈러 역원
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
소수 p와 p보다 작은 자연수 a가 주어질 때, 모듈러 법 p에 대한 a의 곱셈 역원(Modular Multiplicative Inverse)을 구하는 프로그램을 작성하십시오.
즉,
[제약 조건]
• 자연수 $a$, 소수 $p$: $1 \le a < p$, $p \le 10^9$
즉,
(a * x) % p == 1을 만족하는 가장 작은 양의 정수 x를 찾으십시오.[제약 조건]
• 자연수 $a$, 소수 $p$: $1 \le a < p$, $p \le 10^9$
입력 설명
첫째 줄에 자연수 $a$와 소수 $p$가 공백으로 구분되어 주어집니다. ($1 \le a < p$, $p$는 소수, $p \le 10^9$)
출력 설명
$a$의 모듈러 역원을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 7
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5도움
p가 소수이므로 페르마의 소정리(Fermat's Little Theorem)에 의해
a^(p-2) % p가 모듈러 역원이 됩니다.