結果

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

ソースコード

diff # 

import sys
import math

def main():
    N = int(sys.stdin.readline())
    M = int(sys.stdin.readline())
    B = []
    C_mod = []
    for _ in range(M):
        b, c = map(int, sys.stdin.readline().split())
        B.append(b)
        C_mod.append(c % b)  # Compute C_m mod B_m here

    if M == 0:
        print(0 if 0 <= N else "NaN")
        return

    # Initialize with the first congruence
    a = C_mod[0]
    current_modulus = B[0]

    for i in range(1, M):
        c_i = C_mod[i]
        b_i = B[i]

        d = math.gcd(current_modulus, b_i)
        if (a - c_i) % d != 0:
            print("NaN")
            return

        # Compute the new modulus and new_a
        m_div = current_modulus // d
        b_div = b_i // d

        # Calculate modular inverse
        inv = pow(m_div, -1, b_div)

        k = ((c_i - a) // d) * inv
        k %= b_div  # Ensure k is non-negative and within the modulus

        x = a + k * current_modulus
        new_modulus = current_modulus * b_i // d
        a = x % new_modulus
        current_modulus = new_modulus

    if a <= N:
        print(a)
    else:
        print("NaN")

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