题目描述

blablabla

样例

blablabla

算法1

blablabla

时间复杂度

参考文献

Python 代码

from sys import stdin
n = int(input())


def exgcd(a,b,x,y):
    x = 1
    y = 0
    if not b:
        return a, x, y
    d,y,x = exgcd(b, a%b, y, x)
    y -= a//b*x
    return d,x,y

if __name__ == "__main__":
    has_jie = True
    a1,m1 = [int(x) for x in stdin.readline().strip().split(' ')]
    for i in range(n-1):
        a2,m2 = [int(x) for x in stdin.readline().strip().split(' ')]
        k1=0
        k2=0
        d,k1,k2 = exgcd(a1,a2,k1,k2)
        if (m2-m1) % d != 0:
            has_jie = False
            break
        k1 = k1*(m2-m1)//d

        #t = a2//d #C++中防止溢出，每次将K1减小为最小正整数解，Python中可以不用
        #k1 = (k1%t + t)%t

        m1 = a1*k1 + m1
        a1 = abs(a1//d*a2)
    if has_jie:
        print((m1%a1+a1)%a1)

    else:
        print(-1)

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla