結果

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

ソースコード

diff #
raw source code 

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 main():
    N = int(sys.stdin.readline())
    M = int(sys.stdin.readline())
    congruences = []
    for _ in range(M):
        B, C = map(int, sys.stdin.readline().split())
        c = C % B
        congruences.append((B, c))
    
    a = 0
    m = 1
    for (B, c) in congruences:
        d = math.gcd(m, B)
        if (c - a) % d != 0:
            print("NaN")
            return
        m1 = m // d
        B1 = B // d
        c_div = (c - a) // d
        
        g, x, y = extended_gcd(m1, B1)
        k0 = (c_div * x) % B1
        new_a = a + k0 * m
        new_m = m * B // d
        new_a %= new_m
        a, m = new_a, new_m
    
    if a > N:
        print("NaN")
    else:
        print(a)
    print()

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