結果

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

ソースコード

diff # 

import sys
import math

def extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        g, x, y = extended_gcd(b, a % b)
        return (g, y, x - (a // b) * y)

def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        return None  # inverse doesn't exist
    else:
        return x % m

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    B = []
    C = []
    for _ in range(M):
        b = int(input[ptr])
        c = int(input[ptr+1])
        B.append(b)
        C.append(c)
        ptr += 2
    
    a = 0
    mod = 1
    for m in range(M):
        Bm = B[m]
        Cm = C[m]
        a2 = Cm % Bm
        d = math.gcd(mod, Bm)
        if (a2 - a) % d != 0:
            print("NaN")
            return
        m1d = mod // d
        m2d = Bm // d
        inv = modinv(m1d, m2d)
        numerator = (a2 - a) // d
        k0 = (inv * numerator) % m2d
        x = a + k0 * mod
        new_mod = mod * Bm // d
        new_a = x % new_mod
        a, mod = new_a, new_mod
    
    if a <= N:
        print(a)
    else:
        print("NaN")

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