問題一覧 > 通常問題

No.2183 LCA on Rational Tree

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 15
作問者 : noya2noya2 / テスター : shobonvipshobonvip
1 ProblemId : 8971 / 自分の提出
問題文最終更新日: 2023-01-08 03:00:24

問題文

任意の正の有理数 $u$ について、$u = \dfrac{p}{q}$ となる互いに素な正整数の組 $(p,q)$ が 唯一存在するので、このような $(p,q)$ を $(\ p(u),q(u)\ )$ と表します。

簡単な問題文

頂点集合を $V$, 辺集合を $E$ とするグラフ $G=(V,E)$ を次のように定めます。

    $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$
このグラフは形式的に頂点 $1$ を根とした根付き木とみなせます。

$Q$ 個のクエリが与えられます。 $i$ 番目のクエリでは $u_i,v_i\in V$ が与えられます。 上記の根付き木における頂点 $u_i,v_i$ の最小共通祖先を求めてください。


厳密な問題文

頂点集合を $V$, 辺集合を $E$ とするグラフ $G=(V,E)$ を次のように定めます。

    $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$
$G$ において頂点 $r=\dfrac{10^{100}-1}{10^{100}}$ を含む連結成分は木になります。 その根を $r$ とした根付き木 $T$ について $Q$ 個のクエリに答えてください。

$i$ 番目のクエリでは $T$ の $2$ つの頂点 $u_i,v_i$ が $p(u_i),q(u_i),p(v_i),q(v_i)$ によって与えられます。 $T$ における頂点 $u_i,v_i$ の最小共通祖先を頂点 $l_i$ とするとき、 $p(l_i),q(l_i)$ を求めてください。

制約

  • 入力はすべて整数
  • $1\le Q\le 3\times 10^3$
  • $1\le p(u_i)\lt q(u_i)\le 10^9$ かつ $p(u_i),q(u_i)$ は互いに素 $(1\le i\le Q)$
  • $1\le p(v_i)\lt q(v_i)\le 10^9$ かつ $p(v_i),q(v_i)$ は互いに素 $(1\le i\le Q)$
  • 入力

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

    出力

    $i$ 番目のクエリの答えが頂点 $l_i$ であるとき、 $p(l_i), q(l_i)$ を空白区切りで出力してください。 クエリ毎に改行してください。

    サンプル

    サンプル1
    入力
    3
    1 2 1 3
    2 5 4 7
    314159265 358979323 271828182 845904523
    出力
    1 2
    2 3
    8 9
    

    頂点 $\dfrac{1}{2}$ と頂点 $\dfrac{1}{3}$ は辺で繋がれています。

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。