[백준] 6064번 카잉 달력 (by Python)

문제

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

6064번: 카잉 달력

 

풀이

from math import gcd
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    m, n, x, y = map(int, input().split())
    if n > m:
        m, n = n, m
        x, y = y, x
    k = x
    y = 0 if n == y else y
    end = (m * n) // gcd(m, n)
    while k <= end:
        if k % n == y:
            break
        k += m
    print(-1 if k > end else k)

나머지를 이용한 문제라는 것을 눈치채는 것이 중요한 문제. 나타낼 수 있는 해의 가짓수는 M과 N의 최소공배수로 정해지고, K는 M으로 나누었을 때 나머지가 X, N으로 나누었을 때 나머지가 Y인 수이다. 그렇기 때문에 M과 N의 최소공배수 범위 내에서 X에서 M씩 증가시키며 N으로 나누었을 때 나머지가 N인 수를 찾았다. M이 클수록 빨리 찾는 데에 유리했기 때문에, 해당사항을 보장해주는 코드 또한 포함하였다.