結果
問題 | No.1544 [Cherry 2nd Tune C] Synchroscope |
ユーザー |
|
提出日時 | 2021-06-11 21:40:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 264 ms / 2,000 ms |
コード長 | 819 bytes |
コンパイル時間 | 420 ms |
コンパイル使用メモリ | 82,248 KB |
実行使用メモリ | 72,164 KB |
最終ジャッジ日時 | 2024-12-14 22:50:11 |
合計ジャッジ時間 | 7,344 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
from math import gcd def crt(R,M): def ex_gcd(a,b,c): GCD=gcd(a,b) if GCD>1: if c%GCD!=0: return -1 else: a//=GCD b//=GCD c//=GCD x1,y1,m=1,0,a x2,y2,n=0,1,b while m%n!=0: q=m//n x1,y1,m,x2,y2,n=\ x2,y2,n,x1-q*x2,y1-q*y2,m-q*n return (x2*c,y2*c) N=len(M) for i in range(N-1): D=gcd(M[i],M[i+1]) if (R[i+1]-R[i])%D!=0: return None P,Q=ex_gcd(M[i],M[i+1],D) ret=R[i]+M[i]*((R[i+1]-R[i])//D)*P ret%=M[i]*M[i+1]//D if i!=N-2: R[i+1]=ret M[i+1]=M[i]*M[i+1]//D return ret n,m=map(int,input().split()) a=list(map(int,input().split())) b=list(map(int,input().split())) inf=10**18 ans=inf for i in range(n): for j in range(m): if a[i]==b[j]: try: ret=crt([i,j],[n,m]) ans=min(ans,ret+1) except: continue if ans==inf: ans=-1 print(ans)