結果

問題 No.2119 一般化百五減算
ユーザー roaris
提出日時 2022-11-04 21:32:42
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 829 bytes
コンパイル時間 222 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 88,960 KB
最終ジャッジ日時 2024-07-18 19:15:55
合計ジャッジ時間 4,989 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 20 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
input = sys.stdin.readline
from collections import *
from math import gcd
def extGCD(a, b): #ax+by=gcd(a,b)(x,y)1
if b==0:
return 1, 0
s, t = extGCD(b, a%b)
return t, s-a//b*t
def crt(rs, ms): #x≡rs[0](mod ms[0]),...xx≡r(mod lcm(ms))r
r, m = 0, 1
for i in range(len(rs)):
p, q = extGCD(m, ms[i])
g = gcd(m, ms[i])
if (rs[i]-r)%g!=0:
return -1
t = (rs[i]-r)//g*p%(ms[i]//g)
r += m*t
m *= ms[i]//g
return r%m
N = int(input())
M = int(input())
rs, ms = [], []
for _ in range(M):
B, C = map(int, input().split())
rs.append(C)
ms.append(B)
x = crt(rs, ms)
if x==-1 or x>N:
print('NaN')
else:
print(x)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0