HDU 5524 Subtrees

Problem Description

There is a complete binary tree with N nodes.The subtree of the node i has Ai nodes.How many distinct numbers are there of Ai?

Input

There are multiple test cases, no more than 1000 cases.

For each case contains a single integer N on a line.

(1≤N≤1018)

Output

The output of each case will be a single integer on a line:the number of subtrees that contain different nodes.

Sample Input

5

6

7

8

Sample Output

5

#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 105;
long long T, n, s, t, ans, a[maxn];

int main()
{
    //scanf("%d", &T);
    for (int i = a[0] = 1; i < maxn; i++) a[i] = a[i - 1] << 1;
    for (int i = a[0] = 1; i < maxn; i++) a[i] = a[i] - 1;
    while (scanf("%I64d", &n) != EOF)
    {
        for (int i = 1; i < maxn; i++)
        {
            if (n == a[i]) { ans = i; break; }
            if (a[i] < n && n < a[i + 1])
            {
                long long k = n - a[i];
                if (k + k < a[i] + 1) ans = i - 1; else ans = i;
                int flag = (n & 1) ^ 1;
                for (long long i = n >> 1; i; i >>= 1)
                {
                    ans += flag;
                    if (flag == 0 && i % 2 == 0) flag = 1;
                }
                break;
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}