結果

問題 No.2119 一般化百五減算
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:46:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 876 bytes
コンパイル時間 222 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 87,808 KB
最終ジャッジ日時 2025-06-12 18:46:46
合計ジャッジ時間 5,134 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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()
0