結果

問題 No.1936 Rational Approximation
コンテスト
ユーザー ir5
提出日時 2024-06-16 01:06:27
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 929 bytes
コンパイル時間 363 ms
コンパイル使用メモリ 82,908 KB
実行使用メモリ 90,692 KB
最終ジャッジ日時 2024-06-16 01:06:43
合計ジャッジ時間 14,840 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

from fractions import Fraction


def main():
    p, q = list(map(int, input().split()))
    invp = pow(p, q - 2, q)
    sqrt = min(q, 5 * 10 ** 5)

    # lower
    lower = Fraction(0, 1)

    def go1(x):
        nonlocal lower
        f = Fraction(int(p * x // q), x)
        lower = max(lower, f)

    for x in range(1, sqrt):
        # go1(x)
        go1(q - x)

    for y in range(1, sqrt):
        # px mod q = y
        go1(y * invp % q)

    # upper
    upper = Fraction(p, 1)

    def go2(x):
        nonlocal upper
        f = Fraction(int(p * x // q + 1), x)
        upper = min(upper, f)

    for x in range(1, sqrt):
        go2(x)
        # go2(q - x)

    for y in range(q - sqrt + 1, q):
        # px mod q = y
        go2(y * invp % q)

    import sys
    print(upper, file=sys.stderr)
    print(lower, file=sys.stderr)

    print(upper.numerator + upper.denominator + lower.numerator + lower.denominator)


main()
0