結果
問題 | No.2119 一般化百五減算 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
import sysinput = sys.stdin.readlineN=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]=brxy=(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 mbのときN=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//dif M==1:print(S[0][1]%S[0][0])exit()mb=S[0][0]b=S[0][1]%mbfor 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=kif b>N:print("NaN")exit()print(b)