結果

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

ソースコード

diff #
raw source code 

import sys
from math import gcd

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 main():
    N = int(sys.stdin.readline())
    M = int(sys.stdin.readline())
    congruences = []
    for _ in range(M):
        B, C = map(int, sys.stdin.readline().split())
        congruences.append((B, C))
    
    current_mod = 1
    current_rem = 0
    has_solution = True
    
    for B, C in congruences:
        c = C % B
        d = gcd(current_mod, B)
        if (current_rem - c) % d != 0:
            has_solution = False
            break
        
        m1 = current_mod
        a = current_rem
        m2 = B
        b = c
        
        g, x, y = extended_gcd(m1 // d, m2 // d)
        k0 = ((b - a) // d) * x % (m2 // d)
        new_rem = a + k0 * m1
        new_mod = (m1 * m2) // d
        new_rem %= new_mod
        
        current_rem = new_rem
        current_mod = new_mod
    
    if not has_solution:
        print("NaN")
    else:
        print(current_rem if current_rem <= N else "NaN")

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