카잉 달력

• 문제를 바꿔쓰면 M으로 나눈 나머지가 x이고, N으로 나눈 나머지가 y가 되는 가장 작은 자연수를 찾으라는 연립 선형 합동식문제가 된다.
• 일반적인 연립 선형 합동식의 해법을 적용하면 풀수 있다.
  • M과 N이 서로소가 아닐수도 있으므로 중국인의 나머지 정리를 그냥 사용할수는 없다.
• 식이 2개뿐이고, 범위도 작으므로, 그냥 Mk+x 형태의 모든 자연수들을 N으로 나눠보면서 답을 찾아도 충분히 풀리기는 한다.

"""Solution code for "BOJ 6064. 카잉 달력".

- Problem link: https://www.acmicpc.net/problem/6064
- Solution link: http://www.teferi.net/ps/problems/boj/6064

Tags: [Linear congurences]
"""

from teflib import numtheory


def main():
    T = int(input())
    for _ in range(T):
        M, N, x, y = [int(x) for x in input().split()]
        try:
            a, m = numtheory.linear_congruences((x, y), (M, N),
                                                coprime_moduli=False)
            print(a if a > 0 else a + m)
        except ValueError:
            print('-1')


if __name__ == '__main__':
    main()

• Dependency: teflib.combinatorics.linear_congruences