백준 알고리즘 6064번 카잉 달력(python)

시간 초과 때문에 꽤 많이 틀렸다. 최대한 효율적으로 답을 구해야 한다.

핵심은 x%N == y%N을 만족하는 x, y가 있는지 확인하는 것이다. 

처음에는 이해가 잘 안됬었는데, 생각해보면 x에다 M을 더하면 똑같이 x다. 사실상 x는 고정해두고 y가 조건에 맞는지만 확인하면 된다는 것이다. x를 N으로 나눈 나머지가 y를 N으로 나눈 나머지와 같을 때까지 x에 M을 계속 더해주면 된다.

x%N == y 가 아니라 x%N == y%N인 이유는 x가 N으로 딱 나누어졌을 경우에 나머지가 0이기 때문이다.

x가 M*N보다 커졌는데도 해를 찾지 못했다면 유효하지 못한 표현이므로 -1을 출력한다.

EX) M = 10, N = 12, x = 3, y = 9

1) 3%12 != 9%12

2) 13%12 != 9%12

3) 23%12 != 9%12

4) 33%12 = 9%12 = 9

for _ in range(int(input())):
    M, N, x, y = map(int, input().split())
    f = 1
    while(x <= M*N):
        if x%N == y%N:
            print(x)
            f = 0
            break
        x += M
    if f:
        print(-1)