라떼는 말이야 고등학교 때 합동식을 배웠는데요,,, 요즘은 안 배우나 봅니다 ㅜㅜ 다른 문제 낼걸..
쉽게 말해
(ax+by)%n=r
(cx+dy)%n=s
의 해를 구하면 되는 문제입니다.
조건 3은 답이 무조건 하나만 존재한다는 것을 알려주기 위한 조건으로, 풀 때는 무시하셔도 됩니다.
Sample Input을 예로 들어 설명하자면,
(7x+3y)%16=10
(2x+5y)%16=9
를 만족하는 0 이상 15 이하의 정수 x, y를 구하면 됩니다.
그리고 답은 x=3, y=7일 때 위의 식이 성립됩니다.
구하는 방법은 for문으로 일일이 구해도 시간초과는 안 나게 해두었고, 좀 더 빠르게 구하고 싶다면 연립합동식의 해를 구하는 방법을 찾아보세요
참고로 위의 식은 연립합동식으로
7x+3y ≡ 10 (mod 16)
2x+5y ≡ 9 (mod 16)
으로 표현합니다.
