4513: 【例】【入门】子树的大小(2185)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：7
解决：4
题目描述
有如上图所示的完全二叉树，该二叉树有 个结点，编号从上向下、从左向右以此为 。请问，编号为 的结点所在的子树，包含了多少个结点？
比如，，，则上图中的结点 ，， 以及后面的结点都是不存在的，结点 所在子树中包括的结点有 ，，，，因此结点 的所在子树中共有 个结点。
输入
输入两个整数 ，。 ()
输出
输出结点 所在子树中包含的结点的数目。
样例输入 复制
3 7样例输出 复制
3提示
#include<bits/stdc++.h>
using namespace std;
/*
1.从结点m开始求该结点的右孩子的编号，如果该编号存在，每层满的二叉树的深度+1
从而可以求出除了最后一层以外的每层满的部分的二叉树有多少个结点
2.计算最后一层第1个结点的编号，判断最后一层(不满)是否存在
如果存在，加上最后一层的结点数量
*/
int n,m;
int cnt=0;
int ans=0;
int main(){
cin>>m>>n;
for(int i=m;i<=n;i=2*i+1) {
cnt++;
}
ans=(int)pow(2,cnt)-1;
int s=m*(int)pow(2,cnt);
if (s<=n) ans+=n-s+1;
cout<<ans;
return 0;
}