結果

問題 No.2119 一般化百五減算
ユーザー titiatitia
提出日時 2022-11-05 01:48:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,254 bytes
コンパイル時間 264 ms
コンパイル使用メモリ 81,744 KB
実行使用メモリ 93,008 KB
最終ジャッジ日時 2024-07-18 23:08:19
合計ジャッジ時間 5,234 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 21 TLE * 3 -- * 1
権限があれば一括ダウンロードができます

ソースコード

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

import sys
input = sys.stdin.readline
N=int(input())
M=int(input())
S=[list(map(int,input().split())) for i in range(M)]
S2=set()
for x,y in S:
ma=x
a=y%ma
S2.add((ma,a))
# .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
S=list(S2)
if len(S)==1:
print(S[0][1]%S[0][0])
exit()
mb=S[0][0]
b=S[0][1]%mb
for i in range(1,len(S)):
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