結果
問題 | No.187 中華風 (Hard) |
ユーザー | neterukun |
提出日時 | 2021-05-03 13:50:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 485 ms / 3,000 ms |
コード長 | 1,570 bytes |
コンパイル時間 | 313 ms |
コンパイル使用メモリ | 87,064 KB |
実行使用メモリ | 78,952 KB |
最終ジャッジ日時 | 2023-09-29 09:31:18 |
合計ジャッジ時間 | 10,054 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 93 ms
76,284 KB |
testcase_01 | AC | 91 ms
76,224 KB |
testcase_02 | AC | 436 ms
77,920 KB |
testcase_03 | AC | 420 ms
77,940 KB |
testcase_04 | AC | 485 ms
77,916 KB |
testcase_05 | AC | 478 ms
77,808 KB |
testcase_06 | AC | 477 ms
77,776 KB |
testcase_07 | AC | 481 ms
77,736 KB |
testcase_08 | AC | 412 ms
78,720 KB |
testcase_09 | AC | 415 ms
78,792 KB |
testcase_10 | AC | 413 ms
78,952 KB |
testcase_11 | AC | 479 ms
77,668 KB |
testcase_12 | AC | 471 ms
77,880 KB |
testcase_13 | AC | 308 ms
77,692 KB |
testcase_14 | AC | 307 ms
77,780 KB |
testcase_15 | AC | 382 ms
77,452 KB |
testcase_16 | AC | 387 ms
77,676 KB |
testcase_17 | AC | 77 ms
71,252 KB |
testcase_18 | AC | 88 ms
75,792 KB |
testcase_19 | AC | 74 ms
71,552 KB |
testcase_20 | AC | 388 ms
77,892 KB |
testcase_21 | AC | 74 ms
71,284 KB |
testcase_22 | AC | 471 ms
78,048 KB |
testcase_23 | AC | 74 ms
71,276 KB |
testcase_24 | AC | 73 ms
71,128 KB |
ソースコード
def extended_gcd(a, b): if b == 0: return a, 1, 0 else: g, y, x = extended_gcd(b, a % b) y -= (a // b) * x return g, x, y def mod_inv(a, p): _, x, _ = extended_gcd(a, p) return x % p def pregarner(b, m, MOD): def gcd(a, b): while b: a, b = b, a % b return a res = 1 n = len(b) for i in range(n): for j in range(i): g = gcd(m[i], m[j]) if (b[i] - b[j]) % g != 0: return -1 m[i] //= g m[j] //= g gi = gcd(m[i], g) gj = g // gi while True: g = gcd(gi, gj) gi *= g gj //= g if g == 1: break m[i] *= gi m[j] *= gj b[i] %= m[i] b[j] %= m[j] for i in range(n): res = res * m[i] % MOD return res def garner(a, m, MOD): n = len(m) m = m + [MOD] coeff = [1] * (n + 1) res = [0] * (n + 1) for i in range(n): t = (a[i] - res[i]) * mod_inv(coeff[i], m[i]) % m[i] for j in range(i + 1, n + 1): res[j] = (res[j] + t * coeff[j]) % m[j] coeff[j] = coeff[j] * m[i] % m[j] return res[-1] n = int(input()) info = [list(map(int, input().split())) for i in range(n)] MOD = 10 ** 9 + 7 x, y = list(zip(*info)) x, y = list(x), list(y) lcm = pregarner(x, y, MOD) if sum(x) == 0: print(lcm) elif lcm == -1: print(lcm) else: m = garner(x, y, MOD) print(m)