結果
問題 | No.187 中華風 (Hard) |
ユーザー |
![]() |
提出日時 | 2024-10-24 21:08:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 168 ms / 3,000 ms |
コード長 | 1,003 bytes |
コンパイル時間 | 439 ms |
コンパイル使用メモリ | 82,380 KB |
実行使用メモリ | 76,376 KB |
最終ジャッジ日時 | 2024-10-24 21:08:46 |
合計ジャッジ時間 | 4,312 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#yukicoder 187 中華風(Hard) 多倍長解法#exec gcd#Reference: https://x.com/_miz_tom/status/1842086118990479854exec('def gcd(x, y):\n' +' x, y = abs(x), abs(y)\n' +' if x == 0: return y\n' +' if not (y := y % x): return x\n if not (x := x % y): return y\n' * 300 +' return gcd(x, y)')#exec gcdを使わない版gcd = lambda x, y: gcd(y, x % y) if y else abs(x)def CRT(m1, M1, m2, M2): #smallest n ≡ m1 mod M1 ≡ m2 mod M2if (m1 - m2) % ( G := gcd(M1, M2) ) != 0: return -1return (m2 - m1) * pow(M1 // G, -1, M2 // G) % M2 * M1 // G + m1#入力受取N = int(input())P = [tuple(map(int, input().split())) for _ in range(N)]MOD = 10 ** 9 + 7#CRTを実行rem, mod = 0, 1for Xi, Yi in P:rem = CRT(rem, mod, Xi, Yi)if rem == -1:breakmod = mod * Yi // gcd(mod, Yi)if rem == -1: #解なしprint(-1)elif rem == 0: #正整数を探す → lcm(Yi)print(mod % MOD)else: #remを出力print(rem % MOD)