結果

問題 No.1544 [Cherry 2nd Tune C] Synchroscope
ユーザー moharan627
提出日時 2021-06-11 22:37:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,994 ms / 2,000 ms
コード長 2,030 bytes
コンパイル時間 563 ms
コンパイル使用メモリ 82,016 KB
実行使用メモリ 76,656 KB
最終ジャッジ日時 2024-12-15 00:59:02
合計ジャッジ時間 8,595 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
INF = float('inf')
MOD = 10**9 + 7
MOD2 = 998244353
def solve():
def II(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LC(): return list(input())
def IC(): return [int(c) for c in input()]
def MI(): return map(int, sys.stdin.readline().split())
def inv_gcd(a, b):
a = a % b
if a == 0:
return (b, 0)
s = b;
t = a
m0 = 0;
m1 = 1
while (t):
u = s // t
s -= t * u
m0 -= m1 * u
s, t = t, s
m0, m1 = m1, m0
if m0 < 0:
m0 += b // s
return (s, m0)
def inv_mod(x, m):
assert 1 <= m
z = inv_gcd(x, m)
assert z[0] == 1
return z[1]
def crt(r, m):
assert len(r) == len(m)
n = len(r)
r0 = 0;
m0 = 1
for i in range(n):
assert 1 <= m[i]
r1 = r[i] % m[i]
m1 = m[i]
if m0 < m1:
r0, r1 = r1, r0
m0, m1 = m1, m0
if (m0 % m1 == 0):
if (r0 % m1 != r1):
return (0, 0)
continue
g, im = inv_gcd(m0, m1)
u1 = m1 // g
if ((r1 - r0) % g):
return (0, 0)
x = (r1 - r0) // g % u1 * im % u1
r0 += x * m0
m0 *= u1
if r0 < 0:
r0 += m0
return (r0, m0)
N,M = MI()
A = LI()
B = LI()
Ans = INF
C = [N, M]
for a in range(N):
for b in range(M):
if(A[a] == B[b]):
if(a==b):
print(a+1)
exit()
R = [a, b]
r, m = crt(R, C)
if (r == 0 and m == 0):
continue
if (Ans > r + 1):
Ans = r + 1
if(Ans == INF):
print(-1)
exit()
print(Ans)
return
solve()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0