結果
問題 | No.2119 一般化百五減算 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
import sysinput = sys.stdin.readlinefrom collections import *from math import gcddef extGCD(a, b): #ax+by=gcd(a,b)となる(x,y)を1つ求めるif b==0:return 1, 0s, t = extGCD(b, a%b)return t, s-a//b*tdef crt(rs, ms): #x≡rs[0](mod ms[0]),...となるxについてx≡r(mod lcm(ms))となるrを求めるr, m = 0, 1for i in range(len(rs)):p, q = extGCD(m, ms[i])g = gcd(m, ms[i])if (rs[i]-r)%g!=0:return -1t = (rs[i]-r)//g*p%(ms[i]//g)r += m*tm *= ms[i]//greturn r%mN = 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)