[파이썬/python] 백준 15995번 잉여역수 구하기

 

 

 

 

문제

 

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

 

 

 

 

 

 

 

입력

 

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

ex)

3 4

 

 

 

 

 

 

 

출력

 

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

ex)

3

 

---

---

 

코드

 

import sys

a,m=map(int, sys.stdin.readline().split())

n=1

while(1):
    if (1+n*m) / a == (1+n*m) // a:
        print((1+n*m)//a)
        break
    n=n+1