걸어가요

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

"""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()

• Dependency: teflib.numtheory.linear_congruences