結果

問題 No.2119 一般化百五減算
ユーザー maguroflymagurofly
提出日時 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

ソースコード

diff #
プレゼンテーションモードにする

main = -> {
N = gets.to_i
M = gets.to_i
pairs = Array.new(M) { gets.split.map(&:to_i) }
ans = 0
lcm = 1
pairs.each do |b, c|
c %= b
if lcm < b
lcm, b = b, lcm
ans, c = c, ans
end
if lcm % b == 0
if ans % b != c
ans = -1
break
end
next
end
g, i = inv_gcd(lcm, b)
u1 = b / g
if (c - ans) % g != 0
ans = -1
break
end
x = (c - ans) / g % u1 * i % u1
ans += x * lcm
lcm *= u1
ans %= lcm
if ans > N
ans = -1
break
end
end
if ans != -1
puts ans
else
puts "NaN"
end
}
def inv_gcd(a, b)
a %= b
return [b, 0] if a == 0
s, t, x, y = b, a, 0, 1
while t != 0
u = s / t
s -= t * u
x -= y * u
s, t, x, y = t, s, y, x
end
x += b / s if x < 0
[s, x]
end
main.call
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0