中南oj 1213: 二叉树结点公共祖先

1213: 二叉树结点公共祖先

Time Limit: 1 Sec Memory Limit: 128 MB Submit: 159 Solved: 87 [Submit][Status][Web Board]

Description

一个顺序存储的完全二叉树：

2 3

/ /

4 5 6 7

...

任意给定两结点的编号，求两结点最近的公共祖先。

Input

每组数据一行，为空格隔开的两个数i和j，皆为32位有符号正整数

Output

每组数据对应一行，为编号为i和j的结点的最近公共祖先的编号

Sample Input

4 5
4 7

Sample Output

2
1

 1 #include<stdio.h>
 2 
 3 int main()
 4 {
 5     int n,m;
 6     while(scanf("%d%d",&n,&m)>0)
 7     {
 8         if(n==m)
 9         {
10             printf("%d
",n);
11             continue;
12         }
13         while(n!=m)
14         {
15             if(n>m) n=n/2;
16             else m=m/2;
17         }
18         printf("%d
",n);
19     }
20     return 0;
21 }