巧克力棒(chocolate)
Time Limit:1000ms Memory Limit:64MB
题目描述
LYK 找到了一根巧克力棒，但是这根巧克力棒太长了，LYK 无法一口吞进去。
具体地，这根巧克力棒长为 n，它想将这根巧克力棒折成 n 段长为 1 的巧克力棒，然后
慢慢享用。
它打算每次将一根长为 k 的巧克力棒折成两段长为 a 和 b 的巧克力棒，此时若 a=b，则
LYK 觉得它完成了一件非常困难的事，并会得到 1 点成就感。
LYK 想知道一根长度为 n 的巧克力棒能使它得到最多几点成就感。
输入格式(chocolate.in)
第一行一个数 n。
输出格式(chocolate.out)
一个数表示答案。
输入样例
7
输出样例
4
数据范围
对于 20%的数据 n<=5。
对于 50%的数据 n<=20。
对于 80%的数据 n<=2000。
对于 100%的数据 n<=1000000000。
样例解释
将 7 掰成 3+4， 将 3 掰成 1+2， 将 4 掰成 2+2 获得 1 点成就感， 将剩下的所有 2 掰成 1+1
获得 3 点成就感。总共 4 点成就感。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long A,B;
int main()
{
scanf("%I64d",&A);
B=A;
while(A)
{
B-=(A%);
A/=;
}
printf("I64d",B); return ;
}
/*
思路（解析）：
发现ans=n-c(n)。c(n)表示n的二进制中1的个数。 粘一个严谨的证明(其实我自己也没认真看)
我们对c(n)进行归纳。
当c(n)=1时，即n=2^k，ans(n)显然=(n-1)。
我们假设c(n)<=x的情况下ans(n)=n-c(n)都成立。
当c(n)=x+1时，我们要证明ans(n)=n-c(n)。
令j为不超过n的2的幂次的最大值，
有ans(n)=ans(n-j)+ans(j)=n-j-(c(n)-1)+j-1=n-c(n)。
即ans(n)的下界为n-c(n)。
将ans(n)分成两个数i,j时有c(i)+c(j)>=c(n)。
当i不等于j时，有ans(n)<=i-c(i)+j-c(j)<=n-c(n)。
当i=j时，有c(i)+c(j)=2*c(n)，
ans(n)<=i-c(i)+j-c(j)+1<=n-c(n)*2+1，c(n)是正整数。
综上，ans(n)的上界也为n-c(n)。假设成立
*/