結果

問題 No.1544 [Cherry 2nd Tune C] Synchroscope
ユーザー KudeKude
提出日時 2021-06-11 22:01:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 609 ms / 2,000 ms
コード長 5,247 bytes
コンパイル時間 429 ms
コンパイル使用メモリ 86,868 KB
実行使用メモリ 82,144 KB
最終ジャッジ日時 2023-08-21 12:26:51
合計ジャッジ時間 22,276 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 164 ms
80,052 KB
testcase_01 AC 165 ms
80,064 KB
testcase_02 AC 165 ms
80,156 KB
testcase_03 AC 271 ms
81,848 KB
testcase_04 AC 468 ms
82,088 KB
testcase_05 AC 329 ms
81,624 KB
testcase_06 AC 378 ms
81,648 KB
testcase_07 AC 374 ms
81,772 KB
testcase_08 AC 300 ms
81,852 KB
testcase_09 AC 182 ms
81,568 KB
testcase_10 AC 365 ms
81,848 KB
testcase_11 AC 322 ms
81,616 KB
testcase_12 AC 293 ms
82,076 KB
testcase_13 AC 184 ms
81,748 KB
testcase_14 AC 441 ms
81,696 KB
testcase_15 AC 491 ms
81,972 KB
testcase_16 AC 266 ms
81,744 KB
testcase_17 AC 220 ms
81,476 KB
testcase_18 AC 187 ms
81,664 KB
testcase_19 AC 196 ms
82,144 KB
testcase_20 AC 435 ms
81,696 KB
testcase_21 AC 220 ms
81,700 KB
testcase_22 AC 188 ms
81,780 KB
testcase_23 AC 609 ms
81,880 KB
testcase_24 AC 606 ms
81,992 KB
testcase_25 AC 604 ms
82,100 KB
testcase_26 AC 608 ms
81,696 KB
testcase_27 AC 607 ms
81,908 KB
testcase_28 AC 606 ms
81,856 KB
testcase_29 AC 607 ms
81,656 KB
testcase_30 AC 604 ms
82,048 KB
testcase_31 AC 605 ms
81,892 KB
testcase_32 AC 604 ms
82,056 KB
testcase_33 AC 542 ms
82,004 KB
testcase_34 AC 163 ms
80,128 KB
testcase_35 AC 164 ms
80,060 KB
testcase_36 AC 171 ms
81,744 KB
testcase_37 AC 165 ms
80,940 KB
testcase_38 AC 605 ms
81,912 KB
testcase_39 AC 602 ms
81,984 KB
testcase_40 AC 604 ms
82,028 KB
testcase_41 AC 605 ms
81,784 KB
testcase_42 AC 594 ms
81,872 KB
testcase_43 AC 577 ms
81,804 KB
testcase_44 AC 579 ms
81,904 KB
testcase_45 AC 596 ms
81,992 KB
testcase_46 AC 581 ms
81,836 KB
testcase_47 AC 593 ms
81,832 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import types

_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder__math_code = """
import typing


def _is_prime(n: int) -> bool:
    '''
    Reference:
    M. Forisek and J. Jancina,
    Fast Primality Testing for Integers That Fit into a Machine Word
    '''

    if n <= 1:
        return False
    if n == 2 or n == 7 or n == 61:
        return True
    if n % 2 == 0:
        return False

    d = n - 1
    while d % 2 == 0:
        d //= 2

    for a in (2, 7, 61):
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = y * y % n
            t <<= 1
        if y != n - 1 and t % 2 == 0:
            return False
    return True


def _inv_gcd(a: int, b: int) -> typing.Tuple[int, int]:
    a %= b
    if a == 0:
        return (b, 0)

    # Contracts:
    # [1] s - m0 * a = 0 (mod b)
    # [2] t - m1 * a = 0 (mod b)
    # [3] s * |m1| + t * |m0| <= b
    s = b
    t = a
    m0 = 0
    m1 = 1

    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u  # |m1 * u| <= |m1| * s <= b

        # [3]:
        # (s - t * u) * |m1| + t * |m0 - m1 * u|
        # <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        # = s * |m1| + t * |m0| <= b

        s, t = t, s
        m0, m1 = m1, m0

    # by [3]: |m0| <= b/g
    # by g != b: |m0| < b/g
    if m0 < 0:
        m0 += b // s

    return (s, m0)


def _primitive_root(m: int) -> int:
    if m == 2:
        return 1
    if m == 167772161:
        return 3
    if m == 469762049:
        return 3
    if m == 754974721:
        return 11
    if m == 998244353:
        return 3

    divs = [2] + [0] * 19
    cnt = 1
    x = (m - 1) // 2
    while x % 2 == 0:
        x //= 2

    i = 3
    while i * i <= x:
        if x % i == 0:
            divs[cnt] = i
            cnt += 1
            while x % i == 0:
                x //= i
        i += 2

    if x > 1:
        divs[cnt] = x
        cnt += 1

    g = 2
    while True:
        for i in range(cnt):
            if pow(g, (m - 1) // divs[i], m) == 1:
                break
        else:
            return g
        g += 1
"""

atcoder._math = types.ModuleType('atcoder._math')
exec(_atcoder__math_code, atcoder._math.__dict__)


_atcoder_math_code = """
import typing

# import atcoder._math


def inv_mod(x: int, m: int) -> int:
    assert 1 <= m

    z = atcoder._math._inv_gcd(x, m)

    assert z[0] == 1

    return z[1]


def crt(r: typing.List[int], m: typing.List[int]) -> typing.Tuple[int, int]:
    assert len(r) == len(m)

    n = len(r)

    # Contracts: 0 <= r0 < m0
    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

        # assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)

        '''
        (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));
        r2 % m0 = r0
        r2 % m1 = r1
        -> (r0 + x*m0) % m1 = r1
        -> x*u0*g % (u1*g) = (r1 - r0) (u0*g = m0, u1*g = m1)
        -> x = (r1 - r0) / g * inv(u0) (mod u1)
        '''

        # im = inv(u0) (mod u1) (0 <= im < u1)
        g, im = atcoder._math._inv_gcd(m0, m1)

        u1 = m1 // g
        # |r1 - r0| < (m0 + m1) <= lcm(m0, m1)
        if (r1 - r0) % g:
            return (0, 0)

        # u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)
        x = (r1 - r0) // g % u1 * im % u1

        '''
        |r0| + |m0 * x|
        < m0 + m0 * (u1 - 1)
        = m0 + m0 * m1 / g - m0
        = lcm(m0, m1)
        '''

        r0 += x * m0
        m0 *= u1  # -> lcm(m0, m1)
        if r0 < 0:
            r0 += m0

    return (r0, m0)


def floor_sum(n: int, m: int, a: int, b: int) -> int:
    assert 1 <= n
    assert 1 <= m

    ans = 0

    if a >= m:
        ans += (n - 1) * n * (a // m) // 2
        a %= m

    if b >= m:
        ans += n * (b // m)
        b %= m

    y_max = (a * n + b) // m
    x_max = y_max * m - b

    if y_max == 0:
        return ans

    ans += (n - (x_max + a - 1) // a) * y_max
    ans += floor_sum(y_max, a, m, (a - x_max % a) % a)

    return ans
"""

atcoder.math = types.ModuleType('atcoder.math')
atcoder.math.__dict__['atcoder'] = atcoder
atcoder.math.__dict__['atcoder._math'] = atcoder._math
exec(_atcoder_math_code, atcoder.math.__dict__)
inv_mod = atcoder.math.inv_mod

from math import gcd
# from atcoder.math import inv_mod
# import numpy as np
# from numba import njit, i4

# @njit(i4(i4, i4, i4, i4, i4, i4[:], i4[:]))
def main(n, m, g, m2, n2_inv, a, b):
    ans = 10 ** 9
    for i in range(n):
        for j in range(m):
            if (j - i) % g == 0 and a[i] == b[j]:
               k = n2_inv * (j - i) // g % m2
               ans = min(ans, i + k * n)
            pass
    if ans == 10 ** 9:
        ans = -2
    return ans

n, m = map(int, input().split())
g = gcd(n, m)
n2 = n // g
m2 = m // g
n2_inv = inv_mod(n2, m2)
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = main(n, m, g, m2, n2_inv, a, b)
print(ans + 1)
0