最接近的分数

题目描述

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

在满足 $0\leq p\leq q\leq N$ 且 $\gcd(p,q)=1$ 的整数对 $(p,q)$ 中,找出使 $\left\vert r-\dfrac pq\right\vert$ 最小的那一对。

如果存在多对满足条件的 $(p,q)$,输出 $\dfrac pq$ 值最小的那一对。

输入格式

输入按以下格式从标准输入给出:

$r$
$N$

输出格式

对于满足题目条件的整数对 $(p,q)$,在一行中按顺序以空格分隔输出 $p$ 和 $q$。

样例

0.333
33

1 3

$\left\vert0.333-\dfrac13\right\vert=\dfrac1{3000}$。 不存在 $0\leq p\leq q\leq33$、$\gcd(p,q)=1$ 且满足 $\left\vert0.333-\dfrac pq\right\vert\lt\dfrac1{3000}$ 的整数对,因此输出 1 3。

0.45
5

2 5

$\left\vert0.45-\dfrac12\right\vert=\left\vert0.45-\dfrac25\right\vert=\dfrac1{20}$。 不存在 $0\leq p\leq q\leq5$、$\gcd(p,q)=1$ 且满足 $\left\vert0.45-\dfrac pq\right\vert\lt\dfrac1{20}$ 的整数对,并且 $\dfrac12\gt\dfrac25$,因此输出 2 5。

0.314159265358979323
10000

71 226

$\left\vert0.314159265358979323-\dfrac{71}{226}\right\vert=\dfrac{3014435336501}{113000000000000000000}$。

0.007735339533561113
7203576162

34928144 4515398949

数据范围

• $0\lt r\lt 1$
• $r$ 是至多有 18 位小数的实数。
• $1\leq N\leq 10^{10}$
• $N$ 是整数。