15995. 잉여역수 구하기

[Bronze II] 잉여역수 구하기 - 15995

문제 링크

성능 요약

메모리: 109240 KB, 시간: 108 ms

분류

브루트포스 알고리즘, 수학, 모듈로 곱셈 역원, 정수론

제출 일자

2024년 1월 25일 22:46:07

문제 설명

지민이는 대학교에서 "잉여역수 구하기"라는 강의를 듣고 있는데, 지민이는 정수론을 싫어해서 수업 시간에 그냥 졸다 나왔다. 그래서 혁주에게 "오늘 숙제 뭐야?"라고 물었더니, 혁주가 "서로소인 두 자연수 a와 m의 값이 주어지면 a의 법 m에 대한 잉여역수 a*를 구하는 거야."라고 말했다. 지민이는 수업을 듣지 않아서 잉여역수의 정의를 모른다. 지민이의 숙제를 우리가 대신해 주자.

입력

첫째 줄에 서로소인 두 자연수 a와 m이 사이에 공백을 두고 주어진다. (2 ≤ a, m ≤ 10,000)

출력

첫째 줄에 a의 법 m에 대한 잉여역수 a*를 출력한다. 단, 잉여역수는 무한히 많기 때문에 그 중 자연수이며, 최소인 값을 출력하도록 한다.