SDNU 1306.兑数

Description

 [n≥3] ,定义使A3*A4*…*Ak为整数的k [k≥3]叫做兑数。求取区间[3,x]内所有兑数的和加上4是多少。

Input

输入包含多组数据，每一行是一个数x，x<=2^31。

Output

每组测试数据输出对应的一行答案，每组数据间有两个空行。具体输出格式见样例。

Sample Input

5
10

Sample Output

Case # 1:  8 -ti - hen- shui -


Case # 2:  16 -ti - hen- shui -

Source

Unknown

思路：这世道什么鬼题，我一开始发现了规律：如果x是2的幂次，结果为2*x；否则为x的前一个2的幂次n，结果为2*n。然后很迷茫该怎么找2的幂次才能解决，后来想到了暴力打表：直接输出结果。但还是wa。妈耶，到后来才发现，还需要添加几个很大的数....

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
using namespace std;
#define ll long long

ll x, sum, f[100+8];
int id = 0;

bool rule(int a)
{
    return (a&(a-1))?false:true;
}

void init()
{
    f[0] = 4;
    f[1] = 8;
    f[2] = 16;
    f[3] = 32;
    f[4] = 64;
    f[5] = 128;
    f[6] = 256;
    f[7] = 512;
    f[8] = 1024;
    f[9] = 2048;
    f[10] = 4096;
    f[11] = 8192;
    f[12] = 16384;
    f[13] = 32768;
    f[14] = 65536;
    f[15] = 131072;
    f[16] = 262144;
    f[17] = 524288;
    f[18] = 1048576;
    f[19] = 2097152;
    f[20] = 4194304;
    f[21] = 8388608;
    f[22] = 16777216;
    f[23] = 33554432;
    f[24] = 67108864;
    f[25] = 134217728;
    f[26] = 268435456;
    f[27] = 536870912;
    f[28] = 1073741824;
    f[29] = 2147483648;
    f[30] = 4294967296;
}

int main()
{
    init();
    int ii = 1;
    while(~scanf("%lld", &x))
    {
        sum = 0;
        if(x == 3)
        {
            printf("Case # %d:  4 -ti - hen- shui -


", ii);
            ii++;
            continue;
        }
        ll sign;
        if(rule(x))sum = x*2;
        else
        {
            for(int i = 1; i<31; i++)
            {
//                cout<<f[i]<<"------"<<endl;
                if(f[i]>x)
                {
                    sign = f[i-1];
//                    cout<<sign<<endl;
                    break;
                }
            }
            sum = sign*2;
        }
        printf("Case # %d:  %lld -ti - hen- shui -


", ii, sum);
        ii++;
    }
    return 0;
}