結果

問題 No.1936 Rational Approximation
ユーザー ir5ir5
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 739 ms
90,056 KB
testcase_01 AC 697 ms
90,112 KB
testcase_02 AC 708 ms
90,364 KB
testcase_03 AC 905 ms
90,368 KB
testcase_04 AC 880 ms
90,076 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 909 ms
90,228 KB
testcase_11 AC 905 ms
90,240 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 130 ms
88,576 KB
権限があれば一括ダウンロードができます

ソースコード

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