[CLASS 3]백준 6064번 - 카잉 달력

6064번 : 카잉 달력

 

잉카 문명에 관한 이야기와 달력 이야기가 나와 있다. 아마 이게 2012년에 지구가 멸명한다는 이야기의 근원인가..? 그랬던 것 같다.

 

그것과 별개로 이 문제는 나에게 너무 어려웠다.. 결국 풀이를 봤는데 풀이를 보니 이해는 되는데 이걸 어떻게 떠올리지? 같은 느낌이다.

 

import sys
input = sys.stdin.readline

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

    while x <= (m*n):
        if (x-y)%n == 0:
            print(x)
            break
        x += m
    if x > (m*n):
        print(-1)

 

일단 생각해보면 원하는 게 <x:y> 라고 하고 이때가 k번째라고 할때, 앞자리인 x를 맞추기 위해 k는 m으로 나누었을 때 나머지가 x이어야 한다. 예를 들어 x가 3이고 m이 10이라면 k는 적어도 3번째, 13번째, 23번째... 에서 나올 가능성이 있다.

 

이것을 표현하기 위해 x에 계속 m을 더해준다. 그리고 그 x에서 y를 뺐을 때 n으로 나누어 떨어진다면 그 수는 k가 되는것이다. m을 더하는 행위는 m*n까지만 해주면 된다. 정확히는 최소공배수 까지인데, 최소공배수 까지 구하면 시간 초과가 뜬다...

 

중국인의 나머지 정리와 확장 유클리드 호제법을 이용해 푸는 방법도 있다고 하는데... 솔직히 코드를 봐도 어떻게 푸는건지 감이 잘 안잡힌다...

 

wider93님의 코드:

import sys
def euc(x, y):
    q = []
    while y:
        q.append(x // y)
        x, y = y, x % y
    q.pop()
    a, b = 0, 1
    for i in q[::-1]:
        a, b = b, a - i*b
    return x, a, b


def f():
    M, N, x, y = [int(i) for i in sys.stdin.readline().split()]
    d = x-y

    g, a, b = euc(M, N)
    if d % g:
        return -1
    k = d // g
    K = x - k*a*M
    return (K-1) % (M//g*N) + 1


for _ in range(int(sys.stdin.readline())):
    print(f())

 

이게 뭔소린가..?