結果

問題 No.186 中華風 (Easy)
ユーザー ntudantuda
提出日時 2024-07-15 15:43:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 67 ms / 2,000 ms
コード長 3,517 bytes
コンパイル時間 365 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 69,440 KB
最終ジャッジ日時 2024-07-15 15:43:37
合計ジャッジ時間 3,101 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 62 ms
67,860 KB
testcase_01 AC 66 ms
67,816 KB
testcase_02 AC 67 ms
69,116 KB
testcase_03 AC 65 ms
68,120 KB
testcase_04 AC 61 ms
67,796 KB
testcase_05 AC 61 ms
68,304 KB
testcase_06 AC 60 ms
68,196 KB
testcase_07 AC 62 ms
67,600 KB
testcase_08 AC 62 ms
67,792 KB
testcase_09 AC 65 ms
69,064 KB
testcase_10 AC 61 ms
67,724 KB
testcase_11 AC 61 ms
67,688 KB
testcase_12 AC 61 ms
68,864 KB
testcase_13 AC 61 ms
68,988 KB
testcase_14 AC 63 ms
68,416 KB
testcase_15 AC 62 ms
69,440 KB
testcase_16 AC 62 ms
68,148 KB
testcase_17 AC 61 ms
67,532 KB
testcase_18 AC 62 ms
68,736 KB
testcase_19 AC 60 ms
67,532 KB
testcase_20 AC 61 ms
68,576 KB
testcase_21 AC 61 ms
68,900 KB
testcase_22 AC 61 ms
68,336 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import typing
from math import lcm

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

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

    # Contracts: 0 <= r0 < m0
    r0 = 0
    m0 = 1
    for r1, m1 in zip(r, m):
        assert 1 <= m1
        r1 %= m1
        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 = _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)


XY = [list(map(int,input().split())) for _ in range(3)]
X,Y = map(list,zip(*XY))

r,m = crt(X,Y)
if m == 0:
    print(-1)
elif r == 0:
    print(lcm(*Y))
else:
    print(r)
0