結果
問題 | No.2119 一般化百五減算 |
ユーザー |
|
提出日時 | 2022-11-05 00:42:44 |
言語 | Ruby (3.4.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,035 bytes |
コンパイル時間 | 356 ms |
コンパイル使用メモリ | 7,296 KB |
実行使用メモリ | 124,672 KB |
最終ジャッジ日時 | 2024-07-18 22:14:05 |
合計ジャッジ時間 | 11,901 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 TLE * 3 -- * 1 |
コンパイルメッセージ
Syntax OK
ソースコード
main = -> {N = gets.to_iM = gets.to_ipairs = Array.new(M) { gets.split.map(&:to_i) }ans = 0lcm = 1pairs.each do |b, c|c %= bif lcm < blcm, b = b, lcmans, c = c, ansendif lcm % b == 0if ans % b != cans = -1breakendnextendg, i = inv_gcd(lcm, b)u1 = b / gif (c - ans) % g != 0ans = -1breakendx = (c - ans) / g % u1 * i % u1ans += x * lcmlcm *= u1ans %= lcmif ans > Nans = -1breakendendif ans != -1puts anselseputs "NaN"end}def inv_gcd(a, b)a %= breturn [b, 0] if a == 0s, t, x, y = b, a, 0, 1while t != 0u = s / ts -= t * ux -= y * us, t, x, y = t, s, y, xendx += b / s if x < 0[s, x]endmain.call