結果
問題 |
No.2119 一般化百五減算
|
ユーザー |
![]() |
提出日時 | 2025-04-16 00:08:00 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,168 bytes |
コンパイル時間 | 391 ms |
コンパイル使用メモリ | 81,788 KB |
実行使用メモリ | 90,136 KB |
最終ジャッジ日時 | 2025-04-16 00:08:59 |
合計ジャッジ時間 | 5,175 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 TLE * 1 -- * 4 |
ソースコード
import sys import math def main(): N = int(sys.stdin.readline()) M = int(sys.stdin.readline()) B = [] C_mod = [] for _ in range(M): b, c = map(int, sys.stdin.readline().split()) B.append(b) C_mod.append(c % b) # Compute C_m mod B_m here if M == 0: print(0 if 0 <= N else "NaN") return # Initialize with the first congruence a = C_mod[0] current_modulus = B[0] for i in range(1, M): c_i = C_mod[i] b_i = B[i] d = math.gcd(current_modulus, b_i) if (a - c_i) % d != 0: print("NaN") return # Compute the new modulus and new_a m_div = current_modulus // d b_div = b_i // d # Calculate modular inverse inv = pow(m_div, -1, b_div) k = ((c_i - a) // d) * inv k %= b_div # Ensure k is non-negative and within the modulus x = a + k * current_modulus new_modulus = current_modulus * b_i // d a = x % new_modulus current_modulus = new_modulus if a <= N: print(a) else: print("NaN") if __name__ == "__main__": main()