题目描述:
如上所示, 由正整数 1,2,3...... 组成了一颗特殊二叉树. 我们已知这个二叉树的最后一个结点是 n. 现在的问题是, 结点 m 所在的子树中一共包括多少个结点.
比如, n = 12,m = 3 那么上图中的结点 13,14,15 以及后面的结点都是不存在的, 结点 m 所在子树中包括的结点有 3,6,7,12, 因此结点 m 的所在子树中共有 4 个结点.
输入:
输入数据包括多行, 每行给出一组测试数据, 包括两个整数 m,n (1 <= m <= n <= 1000000000). 最后一组测试数据中包括两个 0, 表示输入的结束, 这组数据不用处理.
输出:
对于每一组测试数据, 输出一行, 该行包含一个整数, 给出结点 m 所在子树中包括的结点的数目.
样例输入:
3 12
0 0
样例输出:
- 4
- #include<iostream>
- using namespace std;
- int main(){
- int n,m;
- while(cin>>m>>n && m!=0){
- int num=1;
- if(m==n) {
- num=1;
- }
- else {
- int left=2*m;
- int right=2*m+1;
- while(right<n){
- num+=(right-left+1);
- left=2*left;
- right=2*right+1;
- }
- if(n>=left){
- num+=n-left+1;
- }
- }
- cout<<num<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2788984.html