結果

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

ソースコード

diff # 

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
    B = []
    C = []
    for _ in range(M):
        b = int(input[ptr])
        c = int(input[ptr + 1])
        ptr += 2
        B.append(b)
        # Normalize C
        mod = b
        c_normalized = c % mod
        c_normalized = (c_normalized + mod) % mod  # Ensure non-negative
        C.append(c_normalized)
    
    current_a = 0
    current_m = 1
    
    for i in range(M):
        b = B[i]
        c = C[i]
        d = c - current_a
        g = math.gcd(current_m, b)
        if d % g != 0:
            print("NaN")
            return
        # Solve the equation
        m_prime = current_m // g
        b_prime = b // g
        d_prime = d // g
        if b_prime == 1:
            k0 = 0
        else:
            inv = pow(m_prime, -1, b_prime)
            k0 = (d_prime * inv) % b_prime
        current_a += k0 * current_m
        current_m = current_m * b // g
    
    x_min = current_a % current_m
    if x_min <= N:
        print(x_min)
    else:
        print("NaN")

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