백준: 6064 카잉 달력

문제

6064번: 카잉 달력

 

문제 풀이

 첫 번째 해의 범위가 M, 두 번째 해의 범위가 N이고 현재 년도가 각각 x, y로 주어질 때 몇 번째 해인지 찾는 문제이다. 또한 N, M을 통해 세상의 종말이 도래하는 마지막 해를 구하여야 하는데 이는 N, M의 최소 공배수이다.

 

 예시와 같이 M, N, x, y은 10, 12, 3, 9의 경우 다음과 같이 해당 연도를 구할 수 있다.

x	y
3	3 % 12 = 3
13	13 % 12 = 1
23	23 % 12 = 11
33	33 % 12 = 9

 즉, x 값에 M 값을 더 해준 값에 N으로 나누었을 때 y와 같아지게 되면 정답을 찾을 수 있다. 이는 브루트 포스로 모든 년도를 탐색하는 것과 비교하여 보다 효율적이다. 만약 x의 값이 최소 공배수보다 커진다면, 찾을 수 없는 경우이므로 -1을 반환하면 된다.

 

코드

from sys import stdin
from math import gcd

if __name__ == "__main__":
    t = int(stdin.readline())
    for _ in range(t):
        m, n, x, y = map(int, stdin.readline().split())
        lcm = m * n // gcd(m, n)
    
        while x < lcm:
            if (x - 1) % n + 1 == y:
                break
            x += m

        print(x if x < lcm else -1)