背景

怪盗基德 VS OIBH
第三话

描述

怪盗基德第三次来到熟悉的OIBH总部。屡屡失败的OIBH这次看守的是The Eye of Moon。还是那个
房间，还是那扇门，不同的是OIBH对密码锁进行了改进。这次屏幕上只显示一个数n(基德：这是
改进了还是退化了？）。

密码生成方法：设集合A中A={1,2,...,n}，B为A子集。对于B中任意一个元素x，2x均不在集合B中。

B中元素数目最大值即为密码。

格式

输入格式

一行，一个整数n(1<=n<=maxlongint)

输出格式

只有一个整数m，表示B中元素最大值

样例1

样例输入1

100

样例输出1

67

限制

OIBH在6s内就会发现，所以每个点只有1s时间给你

提示

简单数学题哦~~

来源

From 玛维-影之歌；
感谢vijos的朋友提供数据

暴力可以过4个点，当我再加大数组的时候就炸了。

然后，分治。。。

知道A数组的长度，从后往前取

当长度为奇数是取后半段加上中间的数

然后再取1/4的长度，意思是剩下的二分之一中，后四分之一是不能取得了

当长度为0或1时就加上然后结束。

#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define maxn 10000000long long n,m,l,tot;void q(long long x){    if(x<=1)    {        tot+=x;        return ;    }    if(x%2==1)    {        tot+=x/2+1;        q(x/4);    }    else if(x%2==0)    {        tot+=x/2;        q(x/4);    }}int main(){    scanf("%d",&n);    q(n);    printf("%d",tot);    return 0;}

Vijos 1385盗窃-月之眼