문제

문제 링크 : https://www.acmicpc.net/problem/6064

풀이

카잉 달력의 마지막 해는 연도가 m,n의 최소공배수일 때이다.

처음엔 첫번째 해부터 마지막 해까지 돌면서 연도를 m,n으로 나누고 나머지를 x,y와 비교하는 식으로 풀었다. m,n이 최대 4만까지 가능하기 때문에 당연히 시간 초과가 떴다.

그래서 하나하나 다 탐색하는 방법 말고, m과 n 중 큰 숫자로 연도를 나누었을 때의 나머지가, m으로 나누었을 땐 x와 일치할 때, n으로 나누었을 땐 y와 일치할 때만 탐색을 진행했다. (m이나 n으로만 나눠도 상관 없지만 더 큰 숫자로 나누는 게 더 빠르기 때문에 이렇게 풀었다.)

위의 조건을 만족하는 연도를 m과 n 중 작은 숫자로 나눠서, m으로 나누었을 땐 x와 일치하는지, n으로 나누었을 땐 y와 일치하는지를 검사했다. 만약 일치한다면, 해당 연도가 우리가 찾는 연도이므로 tf = True로 바꿔주고 반복문을 빠져나온다.

만약 마지막 해까지 탐색을 진행했는데 조건을 만족하는 경우가 없다면 tf == False 일 것이다. 따라서 year = -1을 해준다.

마지막으로 year를 출력해준다.

import sys
import math
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    m,n,x,y = map(int,input().split())
    lcm = math.lcm(m,n)
    tf = False
    year = x

    maxMN = max(m, n)
    if maxMN == m:
        xy = (x,y)
    else:
        xy = (y,x)
    minMN = min(m, n)
    
    i = 0
    while True:
        year = xy[0] + i * maxMN

        if year > lcm:
            break
        
        if year % minMN == xy[1]:
            tf = True
            break

        if year % minMN == 0 and xy[1] == minMN:
            tf = True
            break

        i += 1
    if not tf:
        year = -1
    print(year)