103336: [Atcoder]ABC333 G - Nearest Fraction

Problem Statement

You are given a positive real number $r$ less than $1$, and a positive integer $N$.

Among the pair of integers $(p,q)$ such that $0\leq p\leq q\leq N$ and $\gcd(p,q)=1$, find the one that minimizes $\left\vert r-\dfrac pq\right\vert$.

If multiple such pairs $(p,q)$ exist, print the one with the smallest value of $\dfrac pq$.

Constraints

• $0\lt r\lt 1$
• $r$ is given as a real number with at most $18$ decimal places.
• $1\leq N\leq 10^{10}$
• $N$ is an integer.

Input

The input is given from Standard Input in the following format:

$r$
$N$

Output

For the pair $(p,q)$ that satisfies the conditions in the problem statement, print $p$ and $q$ in this order, separated by a space, in a single line.

Sample Input 1

0.333
33

Sample Output 1

1 3

$\left\vert0.333-\dfrac13\right\vert=\dfrac1{3000}$. There is no $0\leq p\leq q\leq33,\gcd(p,q)=1$ such that $\left\vert0.333-\dfrac13\right\vert\lt\dfrac1{3000}$, so print 1 3.

Sample Input 2

0.45
5

Sample Output 2

2 5

$\left\vert0.45-\dfrac12\right\vert=\left\vert0.45-\dfrac25\right\vert=\dfrac1{20}$. There is no $0\leq p\leq q\leq5,\gcd(p,q)=1$ such that $\left\vert0.45-\dfrac pq\right\vert\lt\dfrac1{20}$, and we have $\dfrac12\gt\dfrac25$, so print 2 5.

Sample Input 3

0.314159265358979323
10000

Sample Output 3

71 226

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

Sample Input 4

0.007735339533561113
7203576162

Sample Output 4

34928144 4515398949

问题描述

给你一个小于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$值最小的那对。

约束条件

• $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