[백준/파이썬] 6064번: 카잉 달력

문제

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

풀이

• M,N에 대해 <x:y>가 몇 번째 해인가?
  • x <= M, y <= N

<x:y>의 다음 해는 <x':y'>이다.
x' = x + 1, y' = y + 1
(x > M, y > N = x' = 1, y' = 1)

예제를 보면 이해가 될 겁니다.
M = 10, N = 12일 때,

마지막 해가 60번째 해인 것을 구할 수 있습니다.
마지막 해는 최소공배수를 이용하면 구할 수 있습니다.
LCM(10,12) = 60

여기서 <x:y>는 모듈러 연산을 통해 구할 수 있습니다.
<x:y> = <x % M:y % N>

이를 바탕으로 결과값을 구해보겠읍니다..

x값을 기준으로 (x,y)를 만족하는 결과값(k)을 찾습니다.
x값은 M마다 한 번씩 등장합니다.
k = x, x + M, x + 2M, x + 3M, ...
즉, k = x + tM(t는 상수)

k가 y를 만족하는지 확인합니다.
k % N == y을 만족하는 가장 작은 k를 찾아볼게요.
k에 x + tM을 대입하면, (x + tM) % N == y
즉, tM % N = (y - x) % N을 만족하는 t를 찾아야 합니다.

코드를 작성해보겠읍니다.
최대해 값을 찾기 위해 최소공약수를 구하는 함수부터 작성해볼게요.

def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

def lcm(a,b):
    return a*b // gcd(a,b)

다음으로 위에 구한 공식을 이용해 함수를 작성

def func(m,n,x,y):
    limit = lcm(m,n) # 전체 반복 주기

    while x <= limit: # 값이 전체 주기 이상이면 -1
        if (y-x) % n == 0:
            return x
        x += m # M씩 더해가며 탐색

    return -1

생각보다 어려워서 꽤 오래 걸렸던 문제..😢

코드

import sys
input = sys.stdin.readline

def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

def lcm(a,b):
    return a*b // gcd(a,b)

def func(m,n,x,y):
    limit = lcm(m,n)

    while x <= limit:
        if (y-x) % n == 0:
            return x
        x += m

    return -1

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        m,n,x,y = map(int,input().split())
        print(func(m,n,x,y))