Codeforces Round #647 (Div. 2) C题(结论)两种方法

地址：http://codeforces.com/contest/1362/problem/C

题意：

0~n的数按顺序排列，求二进制相邻差异数之和。

解析：

结论一：

f(n)=f(n/2)+n

1：1

2：3

3：4

4：7

5：8

......

此结论可得出

递归来求f(n)，可以说是很方便了

#include <cstdio>
#include<map>
#include<iostream>
using namespace std;
typedef long long ll;
ll ac(ll n)
{
    if(n==1)
        return 1;
    else if(n==2)
        return 3;
    else
        return ac(n/2)+n;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n ;
        cin>>n;
        cout<<ac(n)<<endl;
    }
}

结论二：

n/1+n/2+n/4+....

n=8:

0000

0001

0010

0011

0100

0101

0110

0111

1000

n=8：从右往左：n/1+n/2+n/4+n/8

所以直接对每一位来算就可以了：

#include <cstdio>
#include<map>
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n ;
        cin>>n;
        ll md=n;
        ll sum=0,k=1;
        while(md)
        {
            sum+=n/k;
            k=k*2;
            md=md/2;
        }
        cout<<sum<<endl;
    }
}