結果
問題 |
No.2119 一般化百五減算
|
ユーザー |
![]() |
提出日時 | 2025-06-12 13:34:53 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 876 bytes |
コンパイル時間 | 187 ms |
コンパイル使用メモリ | 82,908 KB |
実行使用メモリ | 89,192 KB |
最終ジャッジ日時 | 2025-06-12 13:40:33 |
合計ジャッジ時間 | 4,992 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 TLE * 1 -- * 4 |
ソースコード
import sys import math def main(): N = int(sys.stdin.readline()) M = int(sys.stdin.readline()) congruences = [] for _ in range(M): B, C = map(int, sys.stdin.readline().split()) C_mod = C % B congruences.append((B, C_mod)) current_a = 0 current_mod = 1 for B, C in congruences: d = math.gcd(current_mod, B) if (current_a - C) % d != 0: print("NaN") return m1 = current_mod // d b1 = B // d c1 = (C - current_a) // d inv = pow(m1, -1, b1) k0 = (c1 * inv) % b1 x0 = current_a + k0 * current_mod new_mod = current_mod * B // d new_a = x0 % new_mod current_a, current_mod = new_a, new_mod if current_a <= N: print(current_a) else: print("NaN") if __name__ == "__main__": main()