No.2183 LCA on Rational Tree
Problem Statement
For any positive rational number $u$, there exists a unique pair of coprime positive integers $(p,q)$ such that $u = \dfrac{p}{q}$, so we denote this pair $(p,q)$ by $(\ p(u),q(u)\ )$.
Simple Problem Statement
Define a graph $G=(V,E)$ with vertex set $V$ and edge set $E$ as follows.
-
$V=\lbrace u\in \mathbb{Q}_{\gt 0}\ |\ 1\le p(u)\lt q(u) \rbrace$
$\qquad$
$E=\lbrace (u, \dfrac{p(u)+1}{q(u)+1})\ |\ u\in V \rbrace$
You are given $Q$ queries. In the $i$-th query, $u_i,v_i\in V$ are given. Find the lowest common ancestor of vertices $u_i,v_i$ in the rooted tree above.
Formal Problem Statement
Define a graph $G=(V,E)$ with vertex set $V$ and edge set $E$ as follows.
-
$V=\lbrace u\in \mathbb{Q}_{\gt 0}\ |\ 1\le p(u)\lt q(u)\le 10^{10^{100}} \rbrace$
$\qquad$
$E=\lbrace (u, \dfrac{p(u)+1}{q(u)+1})\ |\ u\in V,\ \dfrac{p(u)+1}{q(u)+1}\in V \rbrace$
In the $i$-th query, $2$ vertices $u_i,v_i$ of $T$ are given by $p(u_i),q(u_i),p(v_i),q(v_i)$. Let vertex $l_i$ be the lowest common ancestor of vertices $u_i,v_i$ in $T$. Find $p(l_i),q(l_i)$.
Constraints
Input
$Q$
$p(u_1)$ $q(u_1)$ $p(v_1)$ $q(v_1)$
$p(u_2)$ $q(u_2)$ $p(v_2)$ $q(v_2)$
$\vdots$
$p(u_Q)$ $q(u_Q)$ $p(v_Q)$ $q(v_Q)$
Output
If the answer to the $i$-th query is vertex $l_i$, output $p(l_i), q(l_i)$ separated by a space. Print a newline after each query.
Sample
Sample 1
Input
3 1 2 1 3 2 5 4 7 314159265 358979323 271828182 845904523
Output
1 2 2 3 8 9
Vertex $\dfrac{1}{2}$ and vertex $\dfrac{1}{3}$ are connected by an edge.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2