結果

問題 No.187 中華風 (Hard)
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-15 17:15:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 158 ms / 3,000 ms
コード長 2,585 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 81,692 KB
実行使用メモリ 77,620 KB
最終ジャッジ日時 2023-10-18 12:28:13
合計ジャッジ時間 4,005 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 77 ms
72,088 KB
testcase_01 AC 76 ms
72,088 KB
testcase_02 AC 136 ms
77,468 KB
testcase_03 AC 133 ms
77,500 KB
testcase_04 AC 152 ms
77,268 KB
testcase_05 AC 149 ms
77,268 KB
testcase_06 AC 150 ms
77,268 KB
testcase_07 AC 156 ms
77,620 KB
testcase_08 AC 151 ms
77,268 KB
testcase_09 AC 151 ms
77,272 KB
testcase_10 AC 152 ms
77,268 KB
testcase_11 AC 149 ms
77,272 KB
testcase_12 AC 148 ms
77,272 KB
testcase_13 AC 81 ms
72,788 KB
testcase_14 AC 80 ms
72,788 KB
testcase_15 AC 128 ms
77,256 KB
testcase_16 AC 135 ms
77,472 KB
testcase_17 AC 64 ms
67,812 KB
testcase_18 AC 75 ms
70,040 KB
testcase_19 AC 64 ms
67,812 KB
testcase_20 AC 136 ms
77,300 KB
testcase_21 AC 65 ms
67,812 KB
testcase_22 AC 158 ms
77,540 KB
testcase_23 AC 64 ms
67,812 KB
testcase_24 AC 64 ms
67,812 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)

    MOD = int(1e9 + 7)
    r, m = res
    print(r % MOD if r else m % MOD)
0