6064번 : 카잉 달력 - Python

문제

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

풀이

(count-x)%m==0 and (count-y)%n==0

이 식은 x, y를 달성했을때를 판별하는 식이다. 여기서 count를 1씩 증가시키면 시간초과가 난다. 그렇기 때문에 count를 m으로 증가시키는 것이다.

이 풀이를 해석하자면, 처음 x를 고정시킨 다음에 m으로 x, y를 증가시킨다고 해석하면 된다.

예를 들어 M:10, N:12, X:3, Y:9라고 한다면 X를 3에 고정시킨 상태에서 시작하는 것이다. 그러면 시작할때 count가 3으로 시작하고, 이후에 M씩 더하면 X는 3에 고정될것이다. (3+10)%10 -> 3이기 때문이다. 그렇게 y만 정답에 맞추면 된다.

코드

from sys import stdin, stdout

input = stdin.readline 

t = int(input())

for _ in range(t):
    m, n, x, y = map(int,input().split())
    count = x # x를 맞추고 시작

    while count <= m*n:        
        if (count-x)%m==0 and (count-y)%n==0: # x, y가 둘다 맞다면
            print(count)
            break
        count += m
    else:
        print(-1)