#97 백준 파이썬 [6064] 카잉 달력

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

 

#Solution

이 문제는 반례를 찾는 게 특히 어렵다. 또한 전수조사하여 시간초과가 나는 일을 없애야한다. 1) 반례가 없는가 2) 시간 초과가 나지 않는가? -> O(M*N)은 시간 초과가 난다.

아래는 두 개의 풀이법이고 첫 번째는 시간초과, 두 번째는 시간초과가 나지 않는다.

 

#1 시간초과: 전수 조사하여 x와 y 둘을 만족하는 값을 교집합으로 찾는 식이다.

T = int(input())

def gcd(x,y):
    mod = x % y
    while mod >0:
        x = y
        y = mod
        mod = x % y
    return y    
    
def lcm(x, y):
    return x * y // gcd(x,y)

for t in range(T):
    M, N, x, y = map(int, input().split())
    max_num = lcm(M, N)
    x_set = set()
    y_set = set()
    answer = []
    
    num = 0
    while max_num >= M * num + x:
        x_set.add(M * num + x)
        num += 1
    
    num = 0
    while max_num >= N * num + y:
        y_set.add(N * num + y)
        num += 1
    answer = list(x_set & y_set)
    
    if answer:
        print(answer[0])
    else:
        print(-1)

#2 정답: x를 fix한채 y값만 돌려가며 정답을 확인하는 것이다. 반례를 찾지 못해 고생했는데, y가 최댓값이어서 N이 같은 경우를 걸러내는 조건을 추가해줬다.

def gcd(x,y):
    mod = x % y
    while mod >0:
        x = y
        y = mod
        mod = x % y
    return y    
    
def lcm(x, y):
    return x * y // gcd(x,y)

T = int(input())

for _ in range(T):
    M, N, x, y = map(int, input().split())
    max_num = lcm(M, N)
    i = 0
    
    while M * i + x <= max_num:
        if (M * i + x) % N == y or ((M * i + x) % N == 0 and y == N):
            answer = M * i + x
            break
        answer = -1
        i += 1
    print(answer)