結果
問題 |
No.187 中華風 (Hard)
|
ユーザー |
![]() |
提出日時 | 2024-10-24 21:04:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 503 ms / 3,000 ms |
コード長 | 915 bytes |
コンパイル時間 | 645 ms |
コンパイル使用メモリ | 82,340 KB |
実行使用メモリ | 77,504 KB |
最終ジャッジ日時 | 2024-10-24 21:04:22 |
合計ジャッジ時間 | 7,763 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#yukicoder 187 中華風(Hard) 多倍長解法 #exec gcd #Reference: https://x.com/_miz_tom/status/1842086118990479854 exec('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)') def CRT(n1, M1, n2, M2): #smallest n mod M ≡ n1 mod M1 ≡ n2 mod M2 if (n1 - n2) % ( G := gcd(M1, M2) ) != 0: return (0, 0) return ( (n1 - n2) * pow( c := M2 // G, -1, M1 // G) % M1 * M2 // G + n2, M1 * c ) #入力受取 N = int(input()) P = [tuple(map(int, input().split())) for _ in range(N)] MOD = 10 ** 9 + 7 #CRTを実行 rem, mod = 0, 1 for Xi, Yi in P: rem, mod = CRT(rem, mod, Xi, Yi) if mod == 0: break if mod == 0: #解なし print(-1) elif rem == 0: #正整数を探す → lcm(Yi) print(mod % MOD) else: #remを出力 print(rem % MOD)