a775. 關於防疫的那點小事

內容

在這個疫期很容易傳染的時代，人民的生活漸漸回到了正軌，陽性似乎是人生的必經之路，但即使如此，科學家們還是很努力的研究。

他們發現，傳染路徑會是一個完美二元樹(滿二元樹)，為了方便表示，科學家對感染樹進行中序遍歷然後編號，第一個他們想知道任兩個感染者他們第一個共同的傳染源是誰，如下圖，1與3的共同傳染源者是2，1與2的共同傳染源是2，而3與7的共同傳染源是4。

bit

輸入說明

每筆測資的第一行有一數字$T$，代表有$T$筆測資

接下來$T$行，每行有兩數$A$、$B$，

輸出說明

請輸出$T$行，對每一個$A$、$B$，輸出$A$、$B$共同的感染源。

範例輸入

範例輸出

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (5%): 1.0s , <1M
公開測資點#1 (5%): 1.0s , <1M
公開測資點#2 (5%): 1.0s , <1M
公開測資點#3 (5%): 1.0s , <1M
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <50M
公開測資點#12 (5%): 1.0s , <50M
公開測資點#13 (5%): 1.0s , <50M
公開測資點#14 (5%): 1.0s , <50M
公開測資點#15 (5%): 1.0s , <50M
公開測資點#16 (5%): 1.0s , <50M
公開測資點#17 (5%): 1.0s , <50M
公開測資點#18 (5%): 1.0s , <50M
公開測資點#19 (5%): 1.0s , <50M

提示：

$IO$優化

$55\%$測資，$T \leq 10^5$、$A, B \leq 10^4 $

$45\%$測資，$T \leq 10^6$、$A, B \leq 10^{16} $

標籤:

LCA 位元運算數論

出處:

[管理者：

william1010121 (郭勝威)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」