分数: 625 点
问题陈述
给你一个正实数 r 小于 1,和一个正整数 N.
整数对之间 (p,q) 这样 0\leq p\leq q\leq N 和 \gcd(p,q)=1,找到最小化的那个 \left\vert r-\dfrac pq\right\vert.
如果有多个这样的对 (p,q) 存在,打印最小值 \dfrac pq.
约束
- 0\lt r\lt 1
- r 以实数形式给出,最多 18 小数位。
- 1\leq N\leq 10^{10}
- N 是一个整数。
输入
输入由标准输入按以下格式给出:
r N
输出
对于一对 (p,q) 满足问题陈述中的条件,打印 p 和 q 按此顺序,用空格分隔,在一行中。
示例输入 1
0.333 33
示例输出 1
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.
示例输入 2
0.45 5
示例输出 2
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.
示例输入 3
0.314159265358979323 10000
示例输出 3
71 226
\left\vert0.314159265358979323-\dfrac{71}{226}\right\vert=\dfrac{3014435336501}{113000000000000000000}.
示例输入 4
0.007735339533561113 7203576162
示例输出 4
34928144 4515398949