题目描述

你会得到一个小于 1 的正实数 $r$，以及一个正整数 $N$。

在所有满足 $0 ≤ p ≤ q ≤ N$ 且 $gcd(p, q) = 1$ 的整数对 ($p, q$) 中，找出能使 $∣r− \frac{p}{q}∣$ 的值最小的那一对。

若存在多个这样的整数对 ($p, q$)，则输出其中 $\frac{p}{q}$ ​值最小的那个。

输入格式

输入通过标准输入以下列格式提供：

• $r$
• $N$

输出格式

对于满足题目条件的整数对 $(p, q)$，请按 $p$、$q$ 的顺序输出这两个数，两数之间用空格分隔，单独占一行。

0.333
33

1 3

$∣0.333 − \frac{1}{3} ∣ = \frac{1}{3000}$。不存在满足 $0 ≤ p ≤ q ≤ 33$，最大公约数 $(p, q) = 1$，且使得 $∣0.333 − \frac{p}{1} ∣ < \frac{1}{3}$的整数对，因此输出 1 3。

0.45
5

2 5

$∣0.45 − \frac{1}{2} ∣ = ∣0.45 − \frac{2}{5}∣ = \frac{1}{20}$

0.314159265358979323
10000

71 226

$∣0.314159265358979323 − \frac{71}{226} ∣ = \frac{3014435336501}{113000000000000000000}$

0.007735339533561113
7203576162

34928144 4515398949

数据规模与约定

• $0<r<1$
• $r$ 是一个最多包含 18 位小数的实数。
• $1≤N≤10^10$
• $N$ 是整数。