← 返回题目列表

AtCoder · abc333_g

G. 最近的分数

中文机器翻译题面 查看原题

分数: 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