1. 题目描述

由正整数 1,2,3,… 组成了一棵无限大的（满）二叉树。

从任意一个结点到根结点（编号是 1 的结点）都有一条唯一的路径，比如从 5 到根结点的路径是 (5,2,1)，从 4 到根结点的路径是 (4,2,1)，从根结点 1 到根结点的路径上只包含一个结点 1，因此路径就是 (1)。

对于两个结点 x 和 y，假设他们到根结点的路径分别是 (x1,x2,…,1) 和 (y1,y2,…,1)，那么必然存在两个正整数 i 和 j，使得从 xi 和 yj 开始，有 xi=yj,xi+1=yj+1,xi+2=yj+2,…
现在的问题就是，给定 x 和 y，要求他们的公共父节点，即 xi（也就是 yj）。

样例

// input
10 4
// output
2

2. 思路

对于一个二叉树，定义当前节点的编号为i(从 1 开始)，那么它的左子节点为2*i，右子节点是2*i+1。

故寻找两个节点的公共父节点，可以让其分别除以2，直到两个节点指向同一个位置。

时间复杂度

$O(log_{2}N)$

3. 完整代码

C++

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n,m;
    cin >> n >>m;
    while(n!=m)
    {
        if(n > m)
            n >>= 1;
        else 
            m >>= 1;
    }
    cout << n << endl;
}

Python3

a, b = map(int, input().split(' '))
while a != b:
    if a > b:
        a >>= 1
    else:
        b >>= 1
print(a)