地址：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; } }
Codeforces Round #647 (Div. 2) -Thanks C题(结论)两种方法
原文：https://www.cnblogs.com/liyexin/p/13051308.html