問題一覧 > 通常問題

No.2183 LCA on Rational Tree

レベル : / AI推定難易度 : 1975 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 18
作問者 : noya2 / テスター : shobonvip
お気に入りにしたユーザー ProblemId : 8971 / 自分の提出
問題文最終更新日: 2023-01-08 03:00:24
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

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$
This graph can formally be regarded as a rooted tree with vertex $1$ as its root.

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$
The connected component of $G$ containing the vertex $r=\dfrac{10^{100}-1}{10^{100}}$ is a tree. Answer $Q$ queries about the rooted tree $T$ obtained by taking $r$ as its root.

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

  • All input values are integers.
  • $1\le Q\le 3\times 10^3$
  • $1\le p(u_i)\lt q(u_i)\le 10^9$, and $p(u_i),q(u_i)$ are coprime $(1\le i\le Q)$
  • $1\le p(v_i)\lt q(v_i)\le 10^9$, and $p(v_i),q(v_i)$ are coprime $(1\le i\le Q)$
  • 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もしくは右上の雲マークをクリックしてアカウントを作成してください。