結果

問題 No.187 中華風 (Hard)
ユーザー Yakumo221Yakumo221
提出日時 2024-04-25 09:15:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,180 bytes
コンパイル時間 210 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 77,952 KB
最終ジャッジ日時 2024-11-07 19:49:18
合計ジャッジ時間 3,923 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 75 ms
68,224 KB
testcase_01 AC 75 ms
68,224 KB
testcase_02 AC 96 ms
72,704 KB
testcase_03 AC 98 ms
72,960 KB
testcase_04 AC 126 ms
77,952 KB
testcase_05 AC 126 ms
77,568 KB
testcase_06 AC 125 ms
77,568 KB
testcase_07 AC 123 ms
77,952 KB
testcase_08 AC 129 ms
77,696 KB
testcase_09 AC 127 ms
77,568 KB
testcase_10 AC 129 ms
77,440 KB
testcase_11 AC 128 ms
77,440 KB
testcase_12 AC 125 ms
77,952 KB
testcase_13 AC 75 ms
68,480 KB
testcase_14 AC 76 ms
68,480 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 75 ms
67,328 KB
testcase_18 AC 76 ms
68,096 KB
testcase_19 AC 76 ms
67,328 KB
testcase_20 AC 119 ms
77,440 KB
testcase_21 AC 75 ms
67,328 KB
testcase_22 AC 127 ms
77,824 KB
testcase_23 AC 74 ms
67,712 KB
testcase_24 AC 75 ms
67,328 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

import typing


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

    z = _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)

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


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


n = int(input())

import sys
mp = map(int, sys.stdin.read().split())
ab = list(zip(mp,mp))  

MOD = 1000000007

blist = []
mlist = []

for a,b in ab:
    blist.append(a)
    mlist.append(b)

x,y = crt(blist, mlist)
if x == y == 0:
    print(-1)
else:
    print(x % MOD)
0