結果
問題 | No.2119 一般化百五減算 |
ユーザー | 遭難者 |
提出日時 | 2022-10-11 18:37:09 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 963 bytes |
コンパイル時間 | 314 ms |
コンパイル使用メモリ | 87,216 KB |
実行使用メモリ | 82,268 KB |
最終ジャッジ日時 | 2023-09-07 22:00:45 |
合計ジャッジ時間 | 9,028 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 78 ms
75,824 KB |
testcase_01 | AC | 78 ms
71,384 KB |
testcase_02 | AC | 79 ms
71,352 KB |
testcase_03 | WA | - |
testcase_04 | AC | 78 ms
71,188 KB |
testcase_05 | AC | 79 ms
71,356 KB |
testcase_06 | WA | - |
testcase_07 | AC | 83 ms
71,580 KB |
testcase_08 | WA | - |
testcase_09 | AC | 77 ms
71,204 KB |
testcase_10 | WA | - |
testcase_11 | AC | 79 ms
71,272 KB |
testcase_12 | AC | 78 ms
71,268 KB |
testcase_13 | AC | 79 ms
71,324 KB |
testcase_14 | AC | 80 ms
71,504 KB |
testcase_15 | AC | 78 ms
71,564 KB |
testcase_16 | AC | 79 ms
71,396 KB |
testcase_17 | AC | 80 ms
71,184 KB |
testcase_18 | AC | 79 ms
71,184 KB |
testcase_19 | AC | 80 ms
71,272 KB |
testcase_20 | TLE | - |
testcase_21 | AC | 81 ms
71,464 KB |
testcase_22 | TLE | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
ソースコード
def safe_mod(x, m): x %= m if x < 0: x += m return x def inv_gcd(a, b): a = safe_mod(a, b) if a == 0: return b, 0 s, t = b, a m0, m1 = 0, 1 while t > 0: u = s // t s -= t * u m0 -= m1 * u s, t = t, s m0, m1 = m1, m0 if m0 < 0: m0 += b // s return s, m0 r, m = 0, 1 def crt(rr, mm): global r, m r1, m1 = safe_mod(rr, mm), mm if m < m1: r, r1 = r1, r m, m1 = m1, m if m % m1 == 0: if r % m1 != r1: r = m = 0 return g, im = inv_gcd(m, m1) u1 = m1 // g if (r1 - r) % g != 0: r = m = 0 return x = (r1 - r) // g % u1 * im % u1 r += x * m m *= u1 if r < 0: r += m return max = int(input()) for _ in range(int(input())): b, c = map(int, input().split()) crt(c, b) if m == 0 or r > m: print("NaN") exit() print(r)