結果

問題 No.1936 Rational Approximation
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-15 18:00:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 71 ms / 2,000 ms
コード長 2,008 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 67,196 KB
最終ジャッジ日時 2024-09-18 08:49:54
合計ジャッジ時間 2,101 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 62 ms
67,072 KB
testcase_01 AC 62 ms
66,816 KB
testcase_02 AC 64 ms
66,944 KB
testcase_03 AC 63 ms
67,196 KB
testcase_04 AC 67 ms
66,560 KB
testcase_05 AC 64 ms
66,944 KB
testcase_06 AC 63 ms
66,944 KB
testcase_07 AC 70 ms
67,072 KB
testcase_08 AC 71 ms
66,844 KB
testcase_09 AC 71 ms
66,944 KB
testcase_10 AC 68 ms
66,792 KB
testcase_11 AC 65 ms
66,944 KB
testcase_12 AC 66 ms
67,072 KB
testcase_13 AC 64 ms
66,816 KB
testcase_14 AC 63 ms
66,304 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from typing import Optional, Tuple


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


def exgcdFarey(a: int, b: int) -> Tuple[int, int, int]:
    """ax + by = gcd_ 返回 `(gcd_, x, y)`

    满足解最小, 且 (abs(x)+abs(y), x) 字典序最小
    """
    x1, y1, x2, y2 = farey(a, b)
    x1, y1 = y1, -x1
    x2, y2 = -y2, x2
    g = a * x1 + b * y1
    key1 = (abs(x1) + abs(y1), x1)
    key2 = (abs(x2) + abs(y2), x2)
    if key1 < key2:
        return g, x1, y1
    return g, x2, y2


# Farey 数列 中 a/b 第一次出现的位置的前驱和后继
# a/b = 19/12 → (x1/y1, x2/y2) = (11/7, 8/5) → 返回 (11,7,8,5)
def farey(a: int, b: int) -> Tuple[int, int, int, int]:
    """
    求法雷数列中某一项的的前驱和后继
    https://zhuanlan.zhihu.com/p/323538981
    """
    assert a > 0 and b > 0
    if a == b:
        return 0, 1, 1, 0
    q = (a - 1) // b
    x1, y1, x2, y2 = farey(b, a - q * b)
    return q * x2 + y2, x2, q * x1 + y1, x1


if __name__ == "__main__":
    assert exgcd(2, 3) == (1, -1, 1)
    assert modInv(2, 998244353) == (998244353 + 1) // 2
    # Rational Approximation
    # https://yukicoder.me/problems/no/1936
    p, q = map(int, input().split())
    a, b, c, d = farey(p, q)
    print(a + b + c + d)
0