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

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 15995번 잉여역수 구하기
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

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

• 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요

코드

a, m = map(int, input().split())
i = 1
while True:
    if (1 + i * m) / a == (1 + i * m) // a:
        print((1 + i * m) // a)
        break
    i += 1

설명

문제 자체는 단순하지만, 합동식이나 잉여역수에 대해 처음들어본다면 개념이해에 시간이 걸리는 문제입니다.

저는 정수론을 수강해본적이 없어 해당개념을 아예 처음접했고, 도대체 설명하는 이게 뭘 말하는 것인지를 이해하는데 많은 시간이 걸렸습니다. 일단 이해하고나면 꽤 간단한 개념입니다.

겉핥기식으로나마 배운 개념을 이용하여 설명드리자면, 합동방정식 ax≡1 (mod m)이 성립한다는 것은 적당한 정수 i에 대하여 ax-1=ikm이 성립한다는 뜻이고, 이는 x = (im + 1) / a 라는 뜻입니다(ax를 m으로 나눈 나머지가 1이므로).

이 때, x가 a의 법 m에 대한 잉여역수 a*이므로 x의 값을 출력하면 될 것입니다. x는 나머지이므로 당연히 정수일 것이니, i를 1씩 늘려가며 정수나눗셈 결과와 실수나눗셈 결과가 같은 시점의 값을 출력하면 될 것입니다. 다만, 이렇게 같은지를 비교하는게 실수에 잘못된 값이 저장되어 틀리지 않을까 싶었지만 그대로 통과하더군요(파이썬의 실수 정확도 참고).

실수의 비교에 있어서는 언제나 조심해야 할 것입니다. 아마 해당 문제는 테스트 케이스 중 이런 부분이 문제가 될 만한 케이스가 없는 것으로 추정되며, 후일 만약 데이터가 추가되어 통과되지 않는다면 Decimal을 이용한 비교 혹은 위의 참고 링크에 있는 방법처럼 실수형 오차범위 이내인지 여부를 검사하는 식으로 변경하면 될 것입니다.

---

• 백준 문제풀이 전체 목록 보기

---