結果

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

ソースコード

diff # 

import sys
import math

def main():
    N = int(sys.stdin.readline())
    M = int(sys.stdin.readline())
    pairs = []
    for _ in range(M):
        B, C = map(int, sys.stdin.readline().split())
        pairs.append((B, C))
    
    a = 0
    mod = 1  # current modulus
    
    for B, C in pairs:
        # Adjust C to be non-negative modulo B
        C %= B
        
        d = math.gcd(mod, B)
        if (a - C) % d != 0:
            print("NaN")
            return
        
        # Compute k0, m1, b1
        k0 = (C - a) // d
        m1 = mod // d
        b1 = B // d
        
        # Handle the case where m1 and b1 are both 1
        if m1 == 1 and b1 == 1:
            k = 0
        else:
            # Compute modular inverse of m1 modulo b1
            inv = pow(m1, -1, b1)
            k = (k0 * inv) % b1
        
        x = a + k * mod
        new_mod = mod * B // d
        new_a = x % new_mod
        
        a = new_a
        mod = new_mod
    
    if a <= N:
        print(a)
    else:
        print("NaN")

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