11279: [yosupo] Number Theory - Rational Approximation
[Creator : ]
Description
You are given $T$ test cases. For each case, solve the following problem.
You are given positive integers $N, x, y$.
Let $S$ be the set of irreducible fractions whose numerator and denominator are both positive integers less than or equal to $N$.
Determine the maximum value in $S$ that is less than or equal to $x/y$ ($0/1$ if not exist) and the minimum value in $S$ that is greater than or equal to $x/y$ ($1/0$ if not exist).
You are given positive integers $N, x, y$.
Let $S$ be the set of irreducible fractions whose numerator and denominator are both positive integers less than or equal to $N$.
Determine the maximum value in $S$ that is less than or equal to $x/y$ ($0/1$ if not exist) and the minimum value in $S$ that is greater than or equal to $x/y$ ($1/0$ if not exist).
Input
$T$
$N_0$ $x_0$ $y_0$
$N_1$ $x_1$ $y_1$
$\vdots$
$N_{T-1}$ $x_{T-1}$ $y_{T-1}$
$N_0$ $x_0$ $y_0$
$N_1$ $x_1$ $y_1$
$\vdots$
$N_{T-1}$ $x_{T-1}$ $y_{T-1}$
Output
Print $T$ lines. When the values are $a/b$ and $c/d$, output as follows for each line.
$a$ $b$ $c$ $d$
Constraints
- $1 \leq T \leq 10^5$
- $1 \leq N, x, y \leq 10^9$
- $1 \leq N, x, y \leq 10^9$
Sample 1 Input
5
7 3 10
9 3 6
2 7 3
500 314159265 100000000
100000000 198264837 861210737
Sample 1 Output
2 7 1 3
1 2 1 2
2 1 1 0
333 106 355 113
10885117 47282109 14189579 61635830