結果

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

ソースコード

diff #
raw source code 

import math

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    list_bc = []
    for _ in range(M):
        B = int(input[ptr])
        C = int(input[ptr + 1])
        ptr += 2
        list_bc.append((B, C))
    
    x = 0
    mod = 1
    for B, C in list_bc:
        d = (C - x) % B
        g = math.gcd(mod, B)
        if d % g != 0:
            print("NaN")
            return
        
        a_prime = mod // g
        m_prime = B // g
        d_prime = d // g
        
        try:
            inv = pow(a_prime, -1, m_prime)
        except ValueError:
            print("NaN")
            return
        
        k0 = (d_prime * inv) % m_prime
        x += k0 * mod
        mod = (mod * B) // g
    
    x = x % mod
    if x <= N:
        print(x)
    else:
        print("NaN")

if __name__ == "__main__":
    main()
0