11280: [yosupo] Number Theory - Stern–Brocot Tree
[Creator : ]
Description
The following are true for all problems.
- Positive rational number in input/output is represented by irreducible fraction $a/b$.
- Positive rational numbers are identified with nodes in Stern–Brocot Tree (SBT).
- If a node $a/b$ of SBT appears in input, $a, b$ satisfies following constraints: $1\leq a \leq 10^9$ , $1\leq b \leq 10^9$ , $a$ and $b$ are coprime.
$T$ problems related to SBT in the following list are given.
ENCODE_PATH
Represent the path from $1/1$ to $a/b$ in SBT as a string, using `L` for leftward move and `R` for rightward move.
Compress the string using run-length encoding and output it in the following format.
$k$ $c_0$ $n_0$ $c_1$ $n_1$ $\ldots$ $c_{k-1}$ $n_{k-1}$
Here, $c_i$ is `L` or `R`, and $n_i$ is a positive integer representing the number of consecutive $c_i$s.
Input
ENCODE_PATH $a$ $b$
Output
$k$ $c_0$ $n_0$ $c_1$ $n_1$ $\ldots$ $c_{k-1}$ $n_{k-1}$
DECODE_PATH
LCA
Print the LCA $f/g$ of $a/b$ and $c/d$.
Input
LCA $a$ $b$ $c$ $d$
Output
$f$ $g$
ANCESTOR
Print the ancestor $f/g$ of $a/b$ with depth $k$. If it does not exists, just print `-1`.
Constraints
- $1 \leq k\leq 10^9$
Input
ANCESTOR $k$ $a$ $b$
Output
$f$ $g$
RANGE
The set of descendants of a/b forms an open interval of rational numbers.
Print the infimum $f/g$ and the supremum $h/k$ of the interval.
Exceptionally, print `0 1` for a $0$ , `1 0` for a $+\infty$ .
Input
RANGE $a$ $b$
Output
$f$ $g$ $h$ $k$
- Positive rational number in input/output is represented by irreducible fraction $a/b$.
- Positive rational numbers are identified with nodes in Stern–Brocot Tree (SBT).
- If a node $a/b$ of SBT appears in input, $a, b$ satisfies following constraints: $1\leq a \leq 10^9$ , $1\leq b \leq 10^9$ , $a$ and $b$ are coprime.
$T$ problems related to SBT in the following list are given.
ENCODE_PATH
Represent the path from $1/1$ to $a/b$ in SBT as a string, using `L` for leftward move and `R` for rightward move.
Compress the string using run-length encoding and output it in the following format.
$k$ $c_0$ $n_0$ $c_1$ $n_1$ $\ldots$ $c_{k-1}$ $n_{k-1}$
Here, $c_i$ is `L` or `R`, and $n_i$ is a positive integer representing the number of consecutive $c_i$s.
Input
ENCODE_PATH $a$ $b$
Output
$k$ $c_0$ $n_0$ $c_1$ $n_1$ $\ldots$ $c_{k-1}$ $n_{k-1}$
DECODE_PATH
The path from $1/1$ to $a/b$ is given in the format of ENCODE_PATH. Print $a, b$.
Constraints
- $c_i\neq c_{i+1}$
- $1\leq n_i\leq 10^9$
- It is guaranteed that the answer satisfies $1\leq a\leq 10^9$ and $1\leq b\leq 10^9$.
Input
DECODE_PATH $k$ $c_0$ $n_0$ $c_1$ $n_1$ $\ldots$ $c_{k-1}$ $n_{k-1}$
Output
$a$ $b$
LCA
Print the LCA $f/g$ of $a/b$ and $c/d$.
Input
LCA $a$ $b$ $c$ $d$
Output
$f$ $g$
ANCESTOR
Print the ancestor $f/g$ of $a/b$ with depth $k$. If it does not exists, just print `-1`.
Constraints
- $1 \leq k\leq 10^9$
Input
ANCESTOR $k$ $a$ $b$
Output
$f$ $g$
RANGE
The set of descendants of a/b forms an open interval of rational numbers.
Print the infimum $f/g$ and the supremum $h/k$ of the interval.
Exceptionally, print `0 1` for a $0$ , `1 0` for a $+\infty$ .
Input
RANGE $a$ $b$
Output
$f$ $g$ $h$ $k$
Input
$T$
$\text{query}_0$
$\text{query}_1$
$\vdots$
$\text{query}_{T-1}$
$\text{query}_0$
$\text{query}_1$
$\vdots$
$\text{query}_{T-1}$
Output
Print the answer to each problem on a separate line.
Constraints
$1 \leq T \leq 10^5$
Sample 1 Input
10
DECODE_PATH 0
DECODE_PATH 3 R 2 L 1 R 2
ENCODE_PATH 1 1
ENCODE_PATH 5 11
LCA 2 3 3 5
LCA 5439 19294 8291 29410
ANCESTOR 10 1 1
ANCESTOR 300 1000000000 1
RANGE 1 1
RANGE 11 8
Sample 1 Output
1 1
11 4
0
2 L 2 R 4
2 3
148 525
-1
301 1
0 1 1 0
4 3 7 5