코드

import math
t = int(input())

for _ in range(t):
    m, n, x, y = map(int, input().split())

    boolean = False

    # x의 맥스값이 m, n의 최소 공배수 => 둘의 곱보다 당연히 작을 것
    while x <= (m * n) // math.gcd(m, n):
        if x % n == y % n:
            print(x)
            boolean = True
            break
        x += m

    if not boolean:
        print(-1)

문제 해설

문제를 이해하는 것부터 풀이까지 상당히 난관인 문제였다.

카잉 달력

일단 위의 성질을 이해해야 한다.

x의 값이 M과 같거나 클 경우 x’의 값이 그대로 1이 되는데 이 성질은 곧 x라는 정수가 m진수라는 뜻이며 그 중 1의 자리 숫자만 표현하는 것과 같다. 즉, x가 1부터 M-1까지를 한 싸이클이라고 쳤을 때, M번째 x는 x가 그대로 나온다.

따라서 한 싸이클이 돌고 난 뒤의 x값, x + m은 곧 x라고 할 수 있다.

(위의 성질은 y에 대해서도 동일하나 기준은 하나만 있으면 되므로 x로만 진행)

이를 이해하고 나면 간단해진다. 찾고자 하는 (x,y)가 k번째 해일 때, k가 유효한 순서라면 x를 기준으로 매 싸이클이 돌 때마다 x에 m을 더해주고 (x+m) 이 값에 n으로 모듈러 연산해준 값이 y와 동일한지 비교한다. 이 때 같은 값이 있다면 그 때의 x값이 k가 된다.

좀 더 쉽게 이해하자면, x, y가 주어졌을 때 간편하게 x는 문제의 성질을 무시하고 m진수 그대로 쭉 적어보자

카잉 달력

위의 예시를 참고하자면, x가 m을 기준으로 한 싸이클 씩 돌면서 y값과 쌍을 이룬다. 이 때, 모듈러 연산을 해주는 기준값은 n (여기선 12이므로 12진수)이므로, x % n 한 값 중 y (9)와 일치하는 값을 찾으면 <33 : 9>이므로 k는 33이 된다. (33은 33번째 숫자라는 의미와 동일)

단!!! 이때, if문의 조건을 x % n == y로 하면 반례가 있어 에러가 발생한다. 이 부분에서 좀 어려웠는데 테스트 케이스 중, x % n이 완전히 나누어 떨어지는 경우 y가 0이어야만 하는데, 이 문제는 x와 y값이 0이 나올 수가 없으므로 무조건 -1이 출력되는 것 같다. 따라서 이를 해결하기 위해선 x % n == y % n으로 조건을 변경해주면 된다.

댓글남기기

참고