백준 카잉 달력(6064)

카잉 달력

1. 힌트

1) 카잉 달력의 마지막 해 $<M:N>$은 $M$과 $N$의 최소공배수번째 해가 됩니다. $<M:b>$는 $M$일마다 찾아오고 $<a:N>$는 $N$일마다 찾아오므로 $M$과 $N$ 두개 모두 겹치려면 $M$과 $N$의 최소공배수번째 해여야 합니다.

2) $1$번째 해부터 $M$과 $N$의 최소공배수번째 해까지 순회하면서 $<x:y>$를 찾습니다. 만약 $(N,\ M)=(40000,\ 39999)$라면 최소공배수는 약 $1.6 \times 10^9$이므로 시간 안에 돌지 조금 애매합니다.

3) $<a:b>$에서 $a$나 $b$를 $x$나 $y$로 고정하고 마지막 해가 될 때 까지 $M$이나 $N$일씩 더하면서 $<x:b>$ 혹은 $<a:y>$번째 해를 모두 확인하면 조금 최적화 할 수 있습니다.

2. 접근

처음에 문제를 봤을 때, 알고리즘 태그에 중국인의 나머지 정리가 있는 것을 보고 잘 모르는 알고리즘이라서 바로 해설부터 찾아봤었는데, 사실 몰라도 풀 수 있는 문제였습니다.

3. 구현

import sys
input = sys.stdin.readline
print = sys.stdout.write

# 최대공약수
def gcd(a, b):
    if b == 0 : return a
    return gcd(b, a % b)

# 최소공배수
def lcm(a, b) : return a * b // gcd(a, b)

TC = int(input())
for tc in range(TC):
    M, N, x, y = map(int, input().split())
    b = N if x % N == 0 else x % N
    k = x
    L = lcm(M, N)
    while k <= L and b != y:
        b = N if (b + M) % N == 0 else (b + M) % N
        k += M
    print(str(k if b == y else -1))
    print("\n")

1) 시간 복잡도

2) 테스트 케이스

jh05013님의 반례 모음