문제 링크: https://www.acmicpc.net/problem/6064

Thumbnail: Photo by Seiji Seiji (Unsplash)

언젠가 시간을 내서 정수론을 공부해야겠습니다...

풀이

​브루트포스 풀이로 접근했습니다. 기본적인 아이디어는 아래와 같습니다.

# <x:y> = k일때, 어떻게 k를 찾아야 할까?
# 1. 단순 계산
_x, _y = 1, 1
for i in range(1, lcm(M, N) + 1):
    if _x == x and _y == y:
        print(i)
        break
    _x += 1
    _y += 1
    if _x > M:
        _x = 1
    if _y > N:
        _y = 1
    else:
        print(-1)

허나, 이 풀이의 경우 반복 횟수로 인해 시간 초과가 발생합니다. 따라서, 시간 안에 동작하도록 반복 횟수를 줄여야 합니다. 그렇다면, 고려하지 않아도 되는 경우는 반복하지 않게끔 개선해봅시다.

굳이 볼 필요 없는 조건?

​위처럼 1씩 더하게 된다면, x나 y 둘 중 하나라도 같지 않은 경우도 반복하면서 비교하게 됩니다. 그렇다면, 적어도 하나의 값은 같은 경우만 비교한다면 더 적은 횟수만으로 정답을 찾을 수 있지 않을까요?

<\(x\):\(y\)> = \(k\)라 할 때, 아래 풀이에서는 x값이 항상 일정하게끔 \(k = x + d * M\) (d는 임의의 자연수) 로 설정하고 반복했습니다. 이때, k가 <\(x\):\(y\)>가 되었음을 판단하는 조건을 찾아봅시다.

카잉 달력은 <1:1>부터 시작해, <M:N>으로 끝나는 달력입니다. 이때 x와 y 각 자리는 \(1 \le x \le M\), \(1 \le y \le N\)의 범위를 가집니다. 다시 말하면, 카잉 달력의 k번째 해 <\(x\):\(y\)>는 k를 각각 M, N으로 나눈 나머지와 같습니다!

• k를 N으로 나눈 나머지가 y일 때
• \(y = N\)이라면, k를 N으로 나눈 나머지가 0인지

반복문을 모두 돌고 나서도 k를 찾지 못했다면, 이는 주어진 \(M, N\)의 카잉 달력에서 <\(x\):\(y\)>은 존재하지 않는 해입니다.

for _ in range(int(input())):
    M, N, x, y = map(int, input().split())
    # <x:y> = k일때, 어떻게 k를 찾아야 할까?
    # 2. 굳이 1씩 늘려가며 확인해야 하는가?
    # 어짜피 x는 1~M까지 반복하므로, 원래의 x를 k로 놓고 M씩 더해가며 y의 변화를 비교해보자.
    while k <= lcm(M, N):
        if k % N == y or (y == N and k % N == 0):  # (k - y) mod N = 0 과 동일하다. / y가 N일때는 나머지가 0이 나오기 때문에 기존 방식으로 계산할 수 없다.
            print(k)
            break
        k += M
    else:
        res.append("-1")

예외 처리

위 반복문에서, \(M\) 또는 \(N\)이 1인 경우는 반복문이 1회만 동작하게 됩니다.

처음 1회의 반복문에서, \(k = x\) 이므로 \(k \mod N = y\)라는 조건으로 동작하게 되며, 이는 의도한 동작이 아닙니다. 따라서, 이 경우는 반복문의 동작 전에 예외로 처리해주면 됩니다.

\(M = 1\)인 경우의 <\(x\):\(y\)>는 \(y\)와, \(N = 1\)인 경우의 <\(x\):\(y\)>는 \(x\)와, 같습니다.

전체 코드

input = open(0).readline

def gcd(a, b):
    """Greatest Common Divisor. 최대 공약수를 계산합니다. (유클리드 호제법)"""
    if a < b:
        a, b = b, a  # a가 b보다 크도록 한다.
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    """Least Common Multiple. 최소 공배수를 계산합니다."""
    return a * b // gcd(a, b)

res = []
for _ in range(int(input())):
    M, N, x, y = map(int, input().split())
    # <x:y> = k일때, 어떻게 k를 찾아야 할까?
    # 2. 굳이 1씩 늘려가며 확인해야 하는가?
    # 어짜피 x는 1~M까지 반복하므로, 원래의 x를 k로 놓고 M씩 더해가며 y의 변화를 비교해보자.
    if M == 1:
        res.append(str(y))
        continue
    elif N == 1:
        res.append(str(x))
        continue
    k = x
    while k <= lcm(M, N):
        if k % N == y or (y == N and k % N == 0):  # (k - y) mod N = 0 과 동일하다. / y가 N일때는 나머지가 0이 나오기 때문에 기존 방식으로 계산할 수 없다.
            res.append(str(k))
            break
        k += M
    else:
        res.append("-1")
print("\n".join(res))