6064번 파이썬

 

import sys
input = sys.stdin.readline


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

 

아래 방법은 시간 초과 에러가 뜸

위에 방법은 다른 사람의 방법을 참고했는데 다음과 같은 원리를 이용

(k-x)%m = 0

(k-y)%n = 0

따라서 k는 x에서 m을 계속 더한 값이거나 y에서 n을 계속 더한 값이라고 할 수 있음

=> k대신에 x에 m을 계속 더한 값을 넣어보고 그 값에 y를 빼줄 때 n으로 나눠서 0이면 해를 구할 수 있음

(x의 범위는 최대한 크게 m*n으로 설정!)

import sys
input = sys.stdin.readline


t = int(input())
for _ in range(t):
    m,n,x,y=map(int,input().split())
    x_=0
    y_=0
    year=0
    item=[[-1,-1]]
    while True:
        if x_ < m:
            x_+=1
        else:
            x_=1
        if y_ < n:
            y_+=1
        else:
            y_=1
        year+=1
        if x_==x and y_==y:
            print(year)
            break
        elif [x_,y_] in item:
            print(-1)
            break
        item.append([x_,y_])