結果
問題 | No.187 中華風 (Hard) |
ユーザー | okayu29 |
提出日時 | 2023-02-07 12:35:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 683 ms / 3,000 ms |
コード長 | 1,562 bytes |
コンパイル時間 | 382 ms |
コンパイル使用メモリ | 87,176 KB |
実行使用メモリ | 99,924 KB |
最終ジャッジ日時 | 2023-09-18 20:14:28 |
合計ジャッジ時間 | 12,811 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 89 ms
76,260 KB |
testcase_01 | AC | 90 ms
75,944 KB |
testcase_02 | AC | 634 ms
97,000 KB |
testcase_03 | AC | 628 ms
97,688 KB |
testcase_04 | AC | 681 ms
98,252 KB |
testcase_05 | AC | 683 ms
98,632 KB |
testcase_06 | AC | 677 ms
98,216 KB |
testcase_07 | AC | 677 ms
97,128 KB |
testcase_08 | AC | 654 ms
97,076 KB |
testcase_09 | AC | 656 ms
97,116 KB |
testcase_10 | AC | 655 ms
97,192 KB |
testcase_11 | AC | 676 ms
98,176 KB |
testcase_12 | AC | 681 ms
98,312 KB |
testcase_13 | AC | 439 ms
99,500 KB |
testcase_14 | AC | 441 ms
99,924 KB |
testcase_15 | AC | 629 ms
96,996 KB |
testcase_16 | AC | 634 ms
97,012 KB |
testcase_17 | AC | 74 ms
71,340 KB |
testcase_18 | AC | 87 ms
75,876 KB |
testcase_19 | AC | 73 ms
71,532 KB |
testcase_20 | AC | 549 ms
94,692 KB |
testcase_21 | AC | 74 ms
71,564 KB |
testcase_22 | AC | 675 ms
98,260 KB |
testcase_23 | AC | 73 ms
71,340 KB |
testcase_24 | AC | 72 ms
71,500 KB |
ソースコード
from math import gcd import sys sys.setrecursionlimit(10**6) def extgcd(a, b, x1=1, y1=0, x2=0, y2=1): if b == 0: return x1, y1 q = a//b return extgcd(b, a%b, x2 ,y2, x1-x2*q, y1-y2*q) def crt(b, m, md): b = b[:] m = m + [md] N = len(m) M = [[1]*N for i in range(N)] R = [0]*N for i in range(N): for j in range(1, i+1): M[i][j] = (M[i][j-1] * m[j-1]) % m[i] R[i] = extgcd(M[i][i], m[i])[0] % m[i] memo = [[-1]*N for i in range(N)] def rec(i, j): if i == -1: return 0 if memo[i][j] >= 0: return memo[i][j] v = (rec(i-1, j) + M[j][i]*(R[i]*(b[i]-rec(i-1, i))%m[i])) % m[j] memo[i][j] = v return memo[i][j] rec(N-2, N-1) return memo[N-2][N-1], M[N-1][N-1] def pre_garner(b, m): for i in range(len(m)): for j in range(len(m)): if i == j: continue d = gcd(m[i], m[j]) if (b[i]-b[j])%d != 0: return False m[i] //= d while True: v = gcd(m[i], d) if v == 1: break m[i] *= v m[j] //= v d //= v b[i] %= m[i] b[j] %= m[j] return True n = int(input()) a, m = zip(*(tuple(map(int, input().split())) for _ in range(n))) a, m = list(a), list(m) if not pre_garner(a, m): print(-1) exit() x, mm = crt(a, m, 10**9+7) if all(ai==0 for ai in a): print(mm) else: print(x)