結果

問題 No.187 中華風 (Hard)
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-15 17:08:37
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,513 bytes
コンパイル時間 164 ms
コンパイル使用メモリ 81,584 KB
実行使用メモリ 77,752 KB
最終ジャッジ日時 2023-10-18 12:27:45
合計ジャッジ時間 4,378 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 62 ms
67,788 KB
testcase_18 WA -
testcase_19 AC 62 ms
67,788 KB
testcase_20 RE -
testcase_21 WA -
testcase_22 RE -
testcase_23 WA -
testcase_24 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 


from math import gcd
from typing import List, Optional, Tuple


def crt(remains: List[int], mods: List[int]) -> Optional[int]:
    """
    `模数两两互素`的线性同余方程组的最小非负整数解 - 中国剩余定理 (CRT)
    x ≡ remains_i (mod mods_i), mods_i 两两互质且 Πmods_i <= 1e18
    """
    modMul = 1
    for m in mods:
        modMul *= m
    res = 0
    for mod, remain in zip(mods, remains):
        other = modMul // mod
        inv = modInv(other, mod)
        if inv is None:
            return None
        res = (res + remain * other * inv) % modMul
    return res


def excrt(A: List[int], remains: List[int], mods: List[int]) -> Optional[Tuple[int, int]]:
    """
    线性同余方程组的最小非负整数解 - 扩展中国剩余定理 (EXCRT)
    A_i * x ≡ remains_i (mod mods_i), Πmods_i <= 1e18

    Returns:
      Optional[Tuple[int, int]]:
        解为 x ≡ b (mod m)
        有解时返回 (b, m),无解时返回None
    """
    modMul = 1
    res = 0
    for i, mod in enumerate(mods):
        a, b = A[i] * modMul, remains[i] - A[i] * res
        d = gcd(a, mod)
        if b % d != 0:
            return None
        t = rationalMod(b // d, a // d, mod // d)
        if t is None:
            return None
        res += modMul * t
        modMul *= mod // d
    return res % modMul, modMul


def exgcd(a: int, b: int) -> Tuple[int, int, int]:
    """
    求a, b最大公约数,同时求出裴蜀定理中的一组系数x, y,
    满足 x*a + y*b = gcd(a, b)

    ax + by = gcd_ 返回 `(gcd_, x, y)`
    """
    if b == 0:
        return a, 1, 0
    gcd_, x, y = exgcd(b, a % b)
    return gcd_, y, x - a // b * y


def modInv(a: int, mod: int) -> Optional[int]:
    """
    扩展gcd求a在mod下的逆元
    即求出逆元 `inv` 满足 `a*inv ≡ 1 (mod m)`
    """
    gcd_, x, _ = exgcd(a, mod)
    if gcd_ != 1:
        return None
    return x % mod


def rationalMod(a: int, b: int, mod: int) -> Optional[int]:
    """
    有理数取模(有理数取余)
    求 a/b 模 mod 的值
    """
    inv = modInv(b, mod)
    if inv is None:
        return None
    return a * inv % mod


if __name__ == "__main__":
    assert excrt([1, 1, 1], [2, 3, 2], [3, 5, 7]) == (23, 105)
    # https://yukicoder.me/problems/no/187
    n = int(input())
    remains = [0] * n
    mods = [0] * n
    for i in range(n):
        remains[i], mods[i] = map(int, input().split())
    res = excrt([1] * n, remains, mods)
    print(res if res is None else res[0])
0