테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 걸어가요 ======

===== 풀이 =====
  * 모일 수 있는 위치를 P라고 하면, P = Xi + Si*k 이다. 식을 바꿔쓰면, P ≡ Xi (mod Si) 형태의 연립선형합동식이 된다.
  * [[ps:연립_선형_합동식#m_i가_서로소가_아닐_때|연립선형합동식]]을 풀어서 해를 x0 + m*k 형태로 구한 뒤에, 모든 Xi보다 크거나 같은 최소의 해를 찾으면 된다.
  * 시간복잡도는 O(nlog(LCM(S)))


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 34036. 걸어가요".

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

Tags: [linear congruences]
"""

from teflib import numtheory


def main():
    N = int(input())
    x_and_s = [[int(x) for x in input().split()] for _ in range(N)]

    x, s = zip(*x_and_s)
    try:
        pos, lcm = numtheory.linear_congruences(x, s, also_return_lcm=True)
        max_x = max(x for x, s in x_and_s)
        k = (max_x - pos + lcm - 1) // lcm
        answer = pos + lcm * k
        print(answer)
    except ValueError:
        print('-1')


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:numtheory#linear_congruences|teflib.numtheory.linear_congruences]]

{{tag>BOJ ps:problems:boj:골드_3}}