中国余剰定理

yukicoder-187.py

# yukicoder No.187: "中華風 (Hard)" - http://yukicoder.me/problems/no/187
# AC: http://yukicoder.me/submissions/142514

# おおざっぱな解法
# d_0 = 1, x_0 = 0 とする
# A ≡ x_{i-1} (mod d_{i-1}), A ≡ X_i (mod Y_i) について
# 中国余剰定理を利用して次のx_i, d_iを計算していく。
#
# g_i = gcd(d_{i-1}, Y_i)とする。
# d_{i-1}*x + Y_i*y = g_i となるx, yを拡張ユークリッドの互除法で求める。
# この時、(Y_i / g_i)*y ≡ 1 (mod d_{i-1}/g_i), (d_{i-1} / g_i)*x ≡ 1 (mod Y_i/g_i)である。
# 中国余剰定理より、
# A ≡ (Y_i / g_i)*y * x_{i-1} + (d_{i-1} / g_i)*x * X_i (mod d_{i-1}*Y_i/g_i)であることがわかる。
# そして、d_i = d_{i-1}*Y_i / g_i, x_i ≡ A (mod d_i) とする。
# これを繰り返してx_Nまで求めることで□が求まる。
#
# チェックは単純にY_iで割ってみてX_iになるか確認するだけ。
# 正整数なので、□ = 0の時はd_Nが最小値になる。

# g, x, y = extgcd(a, b)
# => x*a + y*b = g
def extgcd(a, b):
    if b:
        d, y, x = extgcd(b, a%b)
        y -= (a/b)*x
        return d, x, y
    else:
        return a, 1, 0

n = input()
d = 1
x = 0
v = []
for i in xrange(n):
    X, Y = map(int, raw_input().split())
    g, a, b = extgcd(d, Y)
    x, d = (Y*b*x + d*a*X)/g, d*(Y / g)
    x = (x + d) % d
    v.append((X, Y))

for X, Y in v:
    if x % Y != X:
        print -1
        exit(0)
if x == 0:
    print d % (10**9+7)
else:
    print x % (10**9+7)