카잉 달력

1. 조건

• T : 테스트 케이스 : 해를 나타냄
  • 1 <= x <= M, 1 <= y <= M,
• : 마지막 해
  • 1 <= M, N <= 40,000
• <x' : y'> : 그 다음 해
  • x < M이면 x' = x + 1,아니라면 x' = 1
  • y < N이면 y' = y + 1,아니라면 y' = 1

2. 출력

• 주어진 가 몇 번째 해인지 출력
• 만약 유효하지 않다면 -1을 출력

3. 방식

• 조건에 따라 까지 다 반복하는 브루트포스의 형태를 사용
  • dictionary를 사용해도 시간 초과
• 최소공배수, 최대공약수를 사용
  • 1부터 찾는다면 시간 초과
• 각각 M, N을 나눈 것이 x, y라는 나머지라는 규칙을 찾아 해결

4. 코드

# 카잉 달력

import math  # 최소공배수를 사용하기 위함


def Cnt(all):
    if M > N:  # 횟수를 줄이기 위해 두 수중 큰 것으로 설정
        i = x  # 시작 초기화
        gap = M  # 큰 수로 반복
    else:
        i = y
        gap = N
    while i <= all:
        if (i - x) % M == 0 and (i - y) % N == 0:  # 두 수의 조건을 만족하면 리턴
            return i
        else:
            i += gap  # 아니라면 갭만큼 더하기
    return -1  # 해가 없으면 -1 리턴


for t in range(int(input())):
    M, N, x, y = map(int, input().split())
    all = math.lcm(M, N)  # 최대공약수가 마지막 해

    print(Cnt(all))

• 중국인의 나머지 정리를 통해 어떠한 해가 있다라고 생각하고 넘어갔다.