[백준] 6064: 카잉달력 (Python)

문제📖

풀이🙏

• M, N의 최소공배수까지 x에 m을 계속 더해나간 값 = y에 n을 계속 더해나간 값일 때가 정답이 되는 해이다.
• M, N, x, y = 10, 12, 3, 9일때
  x가 3인 해는 3, 13, 23, 33번째 해이다.
  y가 9인 해는 9, 21, 33번째 해이다.

코드💻

def gcd(x, y):
    while(y):
        x, y = y, x%y
    return x

def lcm(x,y):
    return (x*y)//gcd(x,y)
    

def solution(M, N, target_x, target_y):
    while target_x <= lcm(M, N):
        if (target_x - target_y) % N == 0:
            return target_x
        target_x += M
    return -1

for _ in range(int(input())):
    M, N, target_x, target_y = map(int, input().split())
    print(solution(M, N, target_x, target_y))