9도 OJ-1113- - 두 갈래 나무.
1401 단어 9도 OJ
시간 제한: 1초
메모리 제한: 32메가바이트
특수 판제: 아니요
제출: 2599
해결 방법: 778
제목 설명:
위에서 보듯이 정수 1, 2, 3.......로 특수한 두 갈래 나무를 이루었다.우리는 이미 이 두 갈래 나무의 마지막 결점이 n이라는 것을 안다.현재의 문제는 결점 m가 있는 자수에 모두 몇 개의 결점이 포함되어 있느냐는 것이다.
예를 들어 n=12, m=3 그러면 위 그림의 결점 13, 14, 15 및 뒤의 결점은 모두 존재하지 않는다. 결점 m가 있는 자수에 포함된 결점은 3, 6, 7, 12이기 때문에 결점 m가 있는 자수에는 모두 4개의 결점이 있다.
입력:
입력 데이터는 여러 줄을 포함하고 각 줄은 두 개의 정수 m, n(1<=m<=n<=100000000)을 포함하는 테스트 데이터를 제공한다.마지막 테스트 데이터에는 두 개의 0이 포함되어 있으며, 입력의 끝을 표시하며, 이 데이터는 처리할 필요가 없다.
출력:
모든 테스트 데이터에 대해 한 줄을 출력하면 이 줄은 하나의 정수를 포함하고 결점 m가 있는 하위 트리에 포함된 결점의 수를 제시한다.
샘플 입력:
3 12
0 0
샘플 출력:
4
제목은 어렵지 않아요. 나무를 세울 필요 없어요. 그냥 층별로 해요.
#include
#include
#include
#include
using namespace std;
int main()
{
int m,n;
int i,_h;
int count0;
int left,right;
while(scanf("%d %d",&m,&n)==2&&m!=0)
{
_h=(int)(log(n)/log(2)+1)-(int)(log(m)/log(2)+1);
left=right=m;
count0=0;
count0+=(int)pow(2,_h)-1;
for(i=0; i<_h i="" left="left*2;" right="right*2+1;" if="" count0="1;" else="" printf="" return=""/>