結果
問題 | No.2119 一般化百五減算 |
ユーザー |
|
提出日時 | 2022-11-05 16:12:23 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,108 bytes |
コンパイル時間 | 209 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 89,596 KB |
最終ジャッジ日時 | 2024-07-19 08:56:06 |
合計ジャッジ時間 | 7,953 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 TLE * 2 -- * 2 |
ソースコード
def I():return int(input())def MAP():return map(int,input().split())def MAPs():return map(str,input().split())def LI(): return list(map(int,input().split()))def TPL(): return tuple(map(int,input().split()))def S():return input()from collections import defaultdict,Counter,dequefrom copy import deepcopyfrom heapq import heapify,heappop,heappushfrom bisect import bisect_left,bisect_rightfrom itertools import accumulate,product,permutations,combinations,combinations_with_replacementfrom math import gcd,ceil,floor,factorial,sqrt,pi,sin,cos,tan,radians,expimport timeimport randominf=float('inf');mod=998244353;Mod=10**9+7dydx=[(1,0),(0,1),(-1,0),(0,-1)]def inv_gcd(a,b):a=a%bif a==0:return (b,0)s=b;t=am0=0;m1=1while(t):u=s//ts-=t*um0-=m1*us,t=t,sm0,m1=m1,m0if m0<0:m0+=b//sreturn (s,m0)def inv_mod(x,m):assert 1<=mz=inv_gcd(x,m)assert z[0]==1return z[1]def crt(r,m):#余り、割る数assert len(r)==len(m)n=len(r)r0=0;m0=1for i in range(n):assert 1<=m[i]r1=r[i]%m[i]m1=m[i]if m0<m1:r0,r1=r1,r0m0,m1=m1,m0if (m0%m1==0):if (r0%m1!=r1):return (0,0)continueg,im=inv_gcd(m0,m1)u1=m1//gif ((r1-r0)%g):return (0,0)x=(r1-r0)//g % u1*im%u1r0+=x*m0m0*=u1if r0<0:r0+=m0return (r0,m0)#ありえない数字だった場合m0が0で返ってくるdef floor_sum(n,m,a,b):ans=0if a>=m:ans+=(n-1)*n*(a//m)//2a%=mif b>=m:ans+=n*(b//m)b%=my_max=(a*n+b)//mx_max=(y_max*m-b)if y_max==0:return ansans+=(n-(x_max+a-1)//a)*y_maxans+=floor_sum(y_max,a,m,(a-x_max%a)%a)return ansn=I()m=I()C=[];B=[]for _ in range(m):b,c=MAP()B.append(b);C.append(c)r0,m0=crt(C,B)if m0==0:print('NaN')else:if r0<=n:print(r0)else:print('NaN')