結果

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

ソースコード

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

import sys
input = sys.stdin.readline
N=int(input())
M=int(input())
S=[list(map(int,input().split())) for i in range(M)]
# .ax+by=gcd(a,b)(x,y)(x,y)gcd(x,y).
def Ext_Euc(a,b,axy=(1,0),bxy=(0,1)): # axy=a*1+b*0,bxy=a*0+b*1,a,b(1,0),(0,1)
q,r=divmod(a,b)
if r==0:
return bxy,b # a*bxy[0]+b*bxy[1]=b
rxy=(axy[0]-bxy[0]*q,axy[1]-bxy[1]*q) # r.
return Ext_Euc(b,r,bxy,rxy)
# 使
def Chirem(a,ma,b,mb): # N=a mod ma,N=b mod mbN=k mod(lcm(ma,mb))k,lcm(ma,mb).
(p,q),d=Ext_Euc(ma,mb)
if (a-b)%d!=0:
return -1 # -1
return (b*ma*p+a*mb*q)//d%(ma*mb//d),ma*mb//d
if M==1:
print(S[0][1]%S[0][0])
exit()
mb=S[0][0]
b=S[0][1]%mb
for i in range(1,M):
ma=S[i][0]
a=S[i][1]%S[i][0]
k=Chirem(a,ma,b,mb)
if k==-1:
print("NaN")
exit()
else:
b,mb=k
if b>N:
print("NaN")
exit()
print(b)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0