AT_abc333_g [ABC333G] Nearest Fraction

题目描述

给定一个小于 $1$ 的正实数 $r$ 和一个正整数 $N$。

请你在所有满足 $0\leq p\leq q\leq N$ 且 $\gcd(p,q)=1$ 的整数对 $(p,q)$ 中，找到使 $|r-\dfrac{p}{q}|$ 最小的那一组 $(p,q)$。

如果存在多个这样的 $(p,q)$，请输出 $\dfrac{p}{q}$ 最小的那一组。

输入格式

输入以以下格式从标准输入给出。

$r$ $N$

输出格式

请输出满足题目条件的 $(p,q)$，以空格分隔，按顺序输出 $p$ 和 $q$。

输入输出样例 #1

输入 #1

0.333
33

输出 #1

1 3

输入输出样例 #2

输入 #2

0.45
5

输出 #2

2 5

输入输出样例 #3

输入 #3

0.314159265358979323
10000

输出 #3

71 226

输入输出样例 #4

输入 #4

0.007735339533561113
7203576162

输出 #4

34928144 4515398949

说明/提示

限制条件

• $0<r<1$
• $r$ 以十进制小数形式给出，小数点后最多 $18$ 位。
• $1\leq N\leq 10^{10}$
• $N$ 是整数

样例解释 1

$\left|0.333-\dfrac{1}{3}\right|=\dfrac{1}{3000}$。不存在满足 $\left|0.333-\dfrac{p}{q}\right|<\dfrac{1}{3000}$ 且 $0\leq p\leq q\leq 33,\gcd(p,q)=1$ 的 $(p,q)$，因此应输出 1 3。

样例解释 2

$\left|0.45-\dfrac{1}{2}\right|=\left|0.45-\dfrac{2}{5}\right|=\dfrac{1}{20}$。不存在满足 $\left|0.45-\dfrac{p}{q}\right|<\dfrac{1}{20}$ 且 $0\leq p\leq q\leq 5,\gcd(p,q)=1$ 的 $(p,q)$，且 $\dfrac{1}{2}>\dfrac{2}{5}$，因此应输出 2 5。

样例解释 3

$\left|0.314159265358979323-\dfrac{71}{226}\right|=\dfrac{3014435336501}{113000000000000000000}$。

由 ChatGPT 4.1 翻译