사용자 도구

사이트 도구


ps:problems:boj:1476

날짜 계산

ps
링크acmicpc.net/…
출처BOJ
문제 번호1476
문제명날짜 계산
레벨실버 5
분류

수학, 정수론

시간복잡도O(1)
사용한 언어Python
제출기록34584KB / 92ms
최고기록52ms
해결날짜2021/01/31

풀이

  • 연립 합동식 {x%15=E, x%28=S, x%19=M} 의 해를 찾는 문제. 모듈러스가 모두 서로소이므로 중국인의 나머지 정리를 그냥 적용하면 된다.
    • 답은 1이상이어야 하므로, 해가 0인 경우에는 따로 처리해야 하는 것에 주의.
  • 모듈러스가 m_1, m_2, …, m_n 일 때, 중국인의 나머지 정리의 시간복잡도는 O(n + sum(log(m_i)))이다. 이 문제에서는 m_i가 이미 문제에서 고정되어 있으므로 그냥 상수로 생각한다면 시간 복잡도는 그냥 O(1)이다.
  • 사실 이 문제에서는 저 모듈러 역원을 구해서 계산하는 표준적인 계산법을 쓰지 않더라도, 답의 범위가 15*28*19=7980 이하의 자연수라는 것을 알 수 있기 때문에, 그냥 1~7980까지 모든 수에 대해서 저 식을 만족하는지 대입해 보는 방법이 실제 수행속도로는 더 빠르다..

코드

"""Solution code for "BOJ 1476. 날짜 계산".

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

from teflib import numtheory

MODS = (15, 28, 19)


def main():
    E, S, M = [int(x) for x in input().split()]
    a, m = numtheory.linear_congruences((E, S, M), MODS, coprime_moduli=True)
    print(a if a > 0 else a + m)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
K P X V D
 
ps/problems/boj/1476.txt · 마지막으로 수정됨: 2022/05/12 03:30 저자 teferi