사용자 도구

사이트 도구


ps:problems:boj:6064

카잉 달력

ps
링크acmicpc.net/…
출처BOJ
문제 번호6064
문제명카잉 달력
레벨실버 1
분류

연립 선형 합동식

시간복잡도O(logNM)
인풋사이즈M<=40,000, N<=40,000
사용한 언어Python
제출기록35820KB / 260ms
최고기록64ms
해결날짜2022/05/10

풀이

  • 문제를 바꿔쓰면 M으로 나눈 나머지가 x이고, N으로 나눈 나머지가 y가 되는 가장 작은 자연수를 찾으라는 연립 선형 합동식문제가 된다.
  • 일반적인 연립 선형 합동식의 해법을 적용하면 풀수 있다.
    • M과 N이 서로소가 아닐수도 있으므로 중국인의 나머지 정리를 그냥 사용할수는 없다.
  • 식이 2개뿐이고, 범위도 작으므로, 그냥 Mk+x 형태의 모든 자연수들을 N으로 나눠보면서 답을 찾아도 충분히 풀리기는 한다.

코드

"""Solution code for "BOJ 6064. 카잉 달력".

- Problem link: https://www.acmicpc.net/problem/6064
- Solution link: http://www.teferi.net/ps/problems/boj/6064

Tags: [Linear congurences]
"""

from teflib import numtheory


def main():
    T = int(input())
    for _ in range(T):
        M, N, x, y = [int(x) for x in input().split()]
        try:
            a, m = numtheory.linear_congruences((x, y), (M, N),
                                                coprime_moduli=False)
            print(a if a > 0 else a + m)
        except ValueError:
            print('-1')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Y Q M L F
 
ps/problems/boj/6064.txt · 마지막으로 수정됨: 2022/05/12 03:02 저자 teferi