백준 6064번 카잉 달력

정보

문제 바로가기 [클릭]

난이도: Silver1

관련 개념: #수학 #정수론 #중국인의 나머지 정리

---

조건

시간 제한	메모리 제한
1 초	256 MB

---

문제

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. 의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

네 개의 정수 M, N, x와 y가 주어질 때, 이 카잉 달력의 마지막 해라고 하면 는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

---

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 은 카잉 달력의 마지막 해를 나타낸다.

---

출력

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 가 k번째 해를 나타내는 것을 의미한다. 만일 에 의해 표현되는 해가 없다면, 즉, 가 유효하지 않은 표현이면, -1을 출력한다.

---

예제 입출력 1

입력

3
10 12 3 9
10 12 7 2
13 11 5 6

출력

33
-1
83

---

코드1(파이썬)

import math
import sys

t = int(sys.stdin.readline())

for _ in range(t):
    m, n, x, y = tuple(map(int, sys.stdin.readline().split()))

    lcm = n * m // math.gcd(n, m)

    x_set = set([i*m + x for i in range(lcm // m)])
    y_set = set([i*n + y for i in range(lcm // n)])
    intersection = x_set.intersection(y_set)
    
    if intersection:
        print(intersection.pop())
    else:
        print(-1)

---

코드2(파이썬)

import math
import sys

t = int(sys.stdin.readline())

for _ in range(t):
    m, n, x, y = tuple(map(int, sys.stdin.readline().split()))
    result = -1
    # y = n인 경우 대비
    y %= n
    # x 자리에 위치하는 몫들의 최대치
    x_quotient_max = n // math.gcd(n, m)
    
    # 몫(q) * m + x = 원래 정수
    # 원래 정수 % n = y
    for q in range(x_quotient_max):
        # 후보가 존재한다면
        if (q*m + x) % n == y:
            result = q*m + x
            break
    
    print(result)

---

특이사항

• 코드1(45,564KB, 4,952ms)
  • 입력받은 x, y를 나머지로 갖는 모든 숫자를 리스트에 저장
  • 각 리스트에 공통 원소 탐색
• 코드2(32,976KB, 1,692ms)
  • 입력받은 x를 나머지로 갖는 숫자 중 최댓값 탐색
  • 몫을 반복하면서 입력받은 y를 나머지로 갖는 숫자 탐색
• 중국인의 나머지 정리를 활용하면 획기적인 메모리 및 수행시간 절약 가능
• 우수 코드1(https://www.acmicpc.net/source/37435910, 32976KB, 756ms)과의 비교

  • import sys
    import math
    input = sys.stdin.readline
    
    TEST_CASE = int(input())
    
    
    def solveCal():
        M, N, x, y = map(int, input().split())
        lcm = int(M / math.gcd(M, N) * N)
    
        if x == M:
            x = 0
        if y == N:
            y = 0
    
        for i in range(x, lcm, M):
            if i == 0:
                continue
            if i % N == y:
                return i
        return -1
    
    
    def solution():
        answer = []
        for _ in range(TEST_CASE):
            answer.append(str(solveCal()))
        print("\n".join(answer))
    
    
    solution()
        
    

  • 코드2의 방식과 유사하지만, 반복문의 형태를 보다 단순화
• 우수 코드2(https://www.acmicpc.net/source/36946527, 29200KB, 68ms)와의 비교

  • import sys
    # extended euclidean algorithm
    def EEA(a,b):
        s1,s2,t1,t2 = 1, 0, 0, 1
        while b:
            q = a//b
            a,b = b,a-q*b
            s1,s2 = s2,s1-q*s2
            t1,t2 = t2,t1-q*t2
        return a,s1,t1
    
    t= int(sys.stdin.readline().rstrip("\n"))
    for _ in range(t):
        n,m,x,y = list(map(int,sys.stdin.readline().rstrip("\n").split(" ")))
        if m>n:
            x,y = y,x
            n,m = m,n
        g,a,b = EEA(n,m)
        lcm = n*m//g
        d = x-y
        if d%g !=0:
            print("-1")
        else:
            K=x-d//g*a*n
            print((K-1)%lcm+1)
    
    

  • 확장된 유클리드 호제법과 중국인 나머지 정리를 활용한 사례
  • 수학 공부가 더 필요해보임…

---

참고문헌

• joonas, “확장 유클리드 알고리즘으로 나머지 연산의 곱셈 역원 구하기”, Joonas’ Note, https://blog.joonas.io/25?category=722678