def Ex_Euclid(a, b):
    if 0 == b:
        x = 1
        y = 0
        q = a
        return x, y, q
    xyq = Ex_Euclid(b, a % b)
    x = xyq[0]
    y = xyq[1]
    q = xyq[2]
    temp = x
    x = y
    y = temp-a//b*y
    return x, y, q


def inv(a, b):
    return Ex_Euclid(a, b)[0]


def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)


def merge(a1, b1, a2, b2):
    d = gcd(b1, b2)
    c = a2-a1
    if c % d:
        return (0, 0, -1)
    c = (c % b2+b2) % b2
    c = int(c/d)
    b1 = int(b1/d)
    b2 = int(b2/d)
    c = c*inv(b1, b2)
    c = c % b2
    c = c*(b1*d)
    c = c+a1
    b3 = b1*b2*d
    a3 = (c % b3+b3) % b3
    return (a3, b3, 1)


def CRT(a_list, b_list, n):
    a1 = a_list[0]
    b1 = b_list[0]
    for i in range(n-1):
        a2 = a_list[i+1]
        b2 = b_list[i+1]
        (aa, bb, flag) = merge(a1, b1, a2, b2)
        if flag == -1:
            return -1
        a1 = aa
        b1 = bb
    ans =(a1 % b1+b1) % b1
    return ans
# def CRT(m_list,r_list,n):
#     M=m_list[0], R=r_list[0]
#     for i in range(n):
#         d=Ex_Euclid(M,m_list[i+1])[0]
#         if (r_list[i+1]-R)%d:
#             return -1
#         x = (r[i] - R) / d * x % (m[i] / d)
#         R += x * M
#         M = M / d * m[i]
#         R %= M
#     if R>0:
#         return R
#     else:
#         return R+M
def main():
    #n=int(input())
    n, m = map(int, input().strip().split())
    a_list = []
    b_list = []
    for i in range(n):
        x, y = map(int, input().strip().split())
        a_list.append(x)
        b_list.append(y)
    ans = CRT(b_list, a_list, n)
    if ans == -1:
        print("he was definitely lying")
    elif ans > m:
        print("he was probably lying")
    else:
        print(int(ans))


if __name__ == '__main__':
    main()

发表评论

电子邮件地址不会被公开。 必填项已用*标注