結果
問題 | No.187 中華風 (Hard) |
ユーザー | keitel339 |
提出日時 | 2021-03-03 01:06:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 267 ms / 3,000 ms |
コード長 | 1,817 bytes |
コンパイル時間 | 240 ms |
コンパイル使用メモリ | 82,576 KB |
実行使用メモリ | 72,876 KB |
最終ジャッジ日時 | 2024-04-14 05:48:45 |
合計ジャッジ時間 | 5,917 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 53 ms
63,152 KB |
testcase_01 | AC | 52 ms
63,500 KB |
testcase_02 | AC | 250 ms
71,344 KB |
testcase_03 | AC | 250 ms
71,008 KB |
testcase_04 | AC | 265 ms
71,288 KB |
testcase_05 | AC | 265 ms
72,208 KB |
testcase_06 | AC | 264 ms
71,924 KB |
testcase_07 | AC | 265 ms
71,932 KB |
testcase_08 | AC | 256 ms
72,020 KB |
testcase_09 | AC | 255 ms
72,384 KB |
testcase_10 | AC | 255 ms
72,876 KB |
testcase_11 | AC | 267 ms
71,296 KB |
testcase_12 | AC | 264 ms
70,988 KB |
testcase_13 | AC | 161 ms
68,640 KB |
testcase_14 | AC | 161 ms
69,660 KB |
testcase_15 | AC | 224 ms
67,204 KB |
testcase_16 | AC | 223 ms
67,296 KB |
testcase_17 | AC | 38 ms
54,360 KB |
testcase_18 | AC | 50 ms
62,076 KB |
testcase_19 | AC | 38 ms
52,324 KB |
testcase_20 | AC | 215 ms
70,240 KB |
testcase_21 | AC | 38 ms
52,260 KB |
testcase_22 | AC | 263 ms
70,896 KB |
testcase_23 | AC | 38 ms
52,464 KB |
testcase_24 | AC | 38 ms
52,728 KB |
ソースコード
def inverse(a, mod): ''' a, mod が互いに素な場合modular逆数を返す ''' assert mod > 0 a %= mod p = mod x, y = 0, 1 while a > 0: n = p // a p, a = a, p % a, x, y = y, x - n * y return x % mod if p == 1 else -1 import math def preprocess_garner(b, m, mod): n = len(m) assert len(b) == n for i in range(n): for j in range(i+1, n): g = math.gcd(m[i], m[j]) if (b[i] - b[j]) % g != 0: return False m[i] //= g m[j] //= g gi = math.gcd(m[i], g) gj = g // gi while True: g = math.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] return True def garner(b, m, mod): ''' 互いに素なmに対してall(x≡b[i](mod, m[i]))を満たす x と m の積を求める。 多倍長整数を回避。O(n^2+nlogn) ''' n = len(m) s = [0] * (n+1) p = [1] * (n+1) m.append(mod) for i in range(n): t = (b[i] - s[i]) * inverse(p[i], m[i]) % m[i] for j in range(i+1, n+1): s[j] = (s[j] + t * p[j]) % m[j] p[j] = p[j] * m[i] % m[j] m.pop() return s[-1], p[-1] n = int(input()) x, y = [0] * n, [0] * n all_zero = True # ans == mod か all0 か区別つかない for i in range(n): x[i], y[i] = map(int, input().split()) if x[i]: all_zero = False mod = 10**9+7 if not preprocess_garner(x, y, mod): print(-1) quit() if all_zero: ans = 1 for i in range(n): ans = ans * y[i] % mod print(ans) quit() ans, lcm = garner(x, y, mod) print(ans)