結果

問題 No.187 中華風 (Hard)
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-15 17:14:32
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,552 bytes
コンパイル時間 268 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 78,492 KB
最終ジャッジ日時 2024-09-18 08:48:55
合計ジャッジ時間 3,613 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 65 ms
72,440 KB
testcase_01 AC 71 ms
72,280 KB
testcase_02 AC 126 ms
77,988 KB
testcase_03 AC 113 ms
78,312 KB
testcase_04 AC 137 ms
78,012 KB
testcase_05 AC 130 ms
77,552 KB
testcase_06 AC 135 ms
78,248 KB
testcase_07 AC 133 ms
78,160 KB
testcase_08 AC 129 ms
77,684 KB
testcase_09 AC 134 ms
78,108 KB
testcase_10 AC 132 ms
78,092 KB
testcase_11 AC 132 ms
78,008 KB
testcase_12 AC 137 ms
78,040 KB
testcase_13 AC 72 ms
73,620 KB
testcase_14 AC 76 ms
73,452 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 57 ms
67,620 KB
testcase_18 AC 66 ms
71,596 KB
testcase_19 AC 56 ms
67,616 KB
testcase_20 AC 116 ms
78,088 KB
testcase_21 AC 56 ms
66,924 KB
testcase_22 AC 137 ms
78,492 KB
testcase_23 AC 54 ms
67,604 KB
testcase_24 AC 55 ms
67,564 KB
権限があれば一括ダウンロードができます

ソースコード

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
        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
        t = rationalMod(b // d, a // d, mod // d)
        if t is None:
            return
        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
    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)
    if res is None:
        print(-1)
        exit(0)
    r, m = res
    print(r % int(1e9 + 7))
0