結果

問題 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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0