結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー PNJ
提出日時 2024-07-26 18:03:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 103 ms / 3,000 ms
コード長 1,617 bytes
コンパイル時間 444 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 72,960 KB
最終ジャッジ日時 2024-07-26 18:03:22
合計ジャッジ時間 3,339 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

def mod_inv(a,mod):
  if mod == 1:
    return 0
  a %= mod
  b,s,t = mod,1,0
  while True:
    if a == 1:
      return s
    t -= (b // a) * s
    b %= a
    if b == 1:
      return t + mod
    s -= (a // b) * t
    a %= b

def gcd_inv(a,mod):
  a %= mod
  b,s,t = mod,1,0
  while True:
    if a == 0:
      return (b,t + mod)
    t -= (b // a) * s
    b %= a
    if b == 0:
      return (a,s)
    s -= (a // b) * t
    a %= b

# (0,0)のとき存在しない.
def garner(Rem,Mod):
  assert (len(Rem) == len(Mod))

  r,m = 0,1
  for i in range(len(Rem)):
    assert (Mod[i])
    Rem[i] %= Mod[i]
    m1,r1 = Mod[i],Rem[i]
    if m < m1:
      m,m1,r,r1 = m1,m,r1,r
    if m % m1 == 0:
      if r % m1 != r1:
        return (0,0)

    g,im = gcd_inv(m,m1)
    y = abs(r1 - r)
    if y % g:
      return (0,0)
    u1 = m1 // g
    y = y // g % u1
    if (r > r1 and y != 0):
      y = u1 - y
    x = y * im % u1
    r += x * m
    m *= u1
  return (r,m)

# Modの中身が互いに素じゃないとダメ
def Garner(Rem,Mod,mod):
  assert (len(Rem) == len(Mod))

  Rem.append(0)
  Mod.append(mod)
  n = len(Mod)
  coffs = [1] * n
  constants = [0] * n
  for i in range(n - 1):
    v = (Rem[i] - constants[i]) * mod_inv(coffs[i],Mod[i]) % Mod[i]
    for j in range(i + 1,n):
      constants[j] = (constants[j] + coffs[j] * v) % Mod[j]
      coffs[j] = (coffs[j] * Mod[i]) % Mod[j]
  return constants[-1]

mod = 10**9 + 7
R,M = [],[]
for i in range(int(input())):
  X,Y = map(int,input().split())
  R.append(X)
  M.append(Y)
r,m = garner(R,M)
if m == 0:
  print(-1)
  exit()
if r:
  print(r % mod)
else:
  print(m % mod)
0