結果

問題 No.1544 [Cherry 2nd Tune C] Synchroscope
ユーザー sangonana
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0