#P13493. [ABC333G] Nearest Fraction

    ID: 12677 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-Stern–Brocot 树二分查找有理数精确运算高精度乘法

[ABC333G] Nearest Fraction

AT_abc333_g [ABC333G] Nearest Fraction

题目描述

给定一个小于 11 的正实数 rr 和一个正整数 NN。

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

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

输入格式

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

rr NN

输出格式

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

输入输出样例 #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<10<r<1
  • rr 以十进制小数形式给出,小数点后最多 1818 位。
  • 1≤N≤10101\leq N\leq 10^{10}
  • NN 是整数

样例解释 1

∣0.333−13∣=13000\left|0.333-\dfrac{1}{3}\right|=\dfrac{1}{3000}。不存在满足 ∣0.333−pq∣<13000\left|0.333-\dfrac{p}{q}\right|<\dfrac{1}{3000} 且 0≤p≤q≤33,gcd⁡(p,q)=10\leq p\leq q\leq 33,\gcd(p,q)=1 的 (p,q)(p,q),因此应输出 1 3。

样例解释 2

$\left|0.45-\dfrac{1}{2}\right|=\left|0.45-\dfrac{2}{5}\right|=\dfrac{1}{20}$。不存在满足 ∣0.45−pq∣<120\left|0.45-\dfrac{p}{q}\right|<\dfrac{1}{20} 且 0≤p≤q≤5,gcd⁡(p,q)=10\leq p\leq q\leq 5,\gcd(p,q)=1 的 (p,q)(p,q),且 12>25\dfrac{1}{2}>\dfrac{2}{5},因此应输出 2 5。

样例解释 3

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