[Python] 6064번 카잉 달력

문제

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

풀이과정

• 입력

  T : 테스트 케이스

  한줄 씩 : M, N, x, y

  1 ≤ x ≤M

  1≤ y ≤N
  

• 출력

  k : <x:y>가 k번째 해를 나타내는 것

  출력 못하면 -1 출력
  

• 접근법

  x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다.

  <10, 12>
  1번째 해 => <1,1>
  2번째 해 => <2,2>
  .........
  10번째 해 => <10,10>
  11번째 해 => <1,11>
  12번째 해 => <2,12>
  13번째 해 => <3,1>
  14 => <4,2>
  15 => <5,3>
  16 => <6,4>
  17 => <7,5>
  18 => <8,6>
  19 => <9,7>
  20 => <10,8>
  21 => <1,9>
  22 => <2,10>
  23 => <3,11>
  24 => <4,12>

  뭔가, x를 기준으로 하는 방법을 찾아보면 될 것 같다.

  M, N, x, y = 10, 12, 3, 9 일 때

  x가 3인 것은 3번째, 13번째, 23번째, 33번째… 이다.

  x, x+M, x+2M, x+3M..

  y가 9인 것은 9번째, 21번째, 33번째… 이다.

  y, y+N, y+2N…

  → x +M… = y + N… 일때

  예제를 봤을 때, 카잉 달력의 마지막은 M과 N의 최소 공배수이다.

  → x는 M * N을 넘을 수 없다.

  구해야할 숫자를 num이라고 하면,

  num = 10 i + x = 12 j + y

  num - x : 10로 나누어 떨어진다.

  num - y : 12로 나누어 떨어진다.
  

    import sys
    input = sys.stdin.readline
    
    def kaing(M, N, x, y):
        num = x
        while num <= M * N :
            if (num - x) % M == 0 and (num - y) % N == 0:
                return num
            num += M 
        return -1
    
    T = int(input())
    for _ in range(T):
        M,N,x,y = map(int, input().split())
        print(kaing(M,N,x,y))