[python] 백준 6064 카잉 달력

https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

 

문제 해결

x+ M*a = y + N*b 를 만족하는 자연수 a,와 b 가 있어야 정상이다. 만약 존재하지 않는다면 -1

그러면 (x + M*a - y) % N = 0 이 되어야 한다.

a는 N 이하이다. N보다 커지면 위의 식( (x + M*a - y) % N)의 나머지가 반복되기 때문에 더 해봤자 존재하지 않는 것이다.

 

CODE

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    m, n, x, y = map(int, input().split())
    while x<= m*n:
        if (x-y)%n == 0:
            print(x)
            break
        x += m
    else:
        print(-1)