結果

問題 No.187 中華風 (Hard)
ユーザー PNJPNJ
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 53 ms
62,336 KB
testcase_01 AC 53 ms
62,464 KB
testcase_02 AC 76 ms
67,072 KB
testcase_03 AC 73 ms
67,072 KB
testcase_04 AC 103 ms
71,680 KB
testcase_05 AC 87 ms
72,256 KB
testcase_06 AC 87 ms
71,936 KB
testcase_07 AC 90 ms
71,936 KB
testcase_08 AC 93 ms
72,960 KB
testcase_09 AC 90 ms
72,448 KB
testcase_10 AC 89 ms
72,320 KB
testcase_11 AC 88 ms
72,192 KB
testcase_12 AC 89 ms
72,320 KB
testcase_13 AC 54 ms
62,464 KB
testcase_14 AC 56 ms
62,976 KB
testcase_15 AC 71 ms
65,664 KB
testcase_16 AC 80 ms
66,432 KB
testcase_17 AC 38 ms
52,096 KB
testcase_18 AC 50 ms
61,184 KB
testcase_19 AC 38 ms
52,352 KB
testcase_20 AC 80 ms
69,248 KB
testcase_21 AC 38 ms
52,096 KB
testcase_22 AC 86 ms
72,064 KB
testcase_23 AC 36 ms
52,096 KB
testcase_24 AC 37 ms
52,352 KB
権限があれば一括ダウンロードができます

ソースコード

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