链接：https://www.nowcoder.com/acm/contest/116/H
来源：牛客网
题目描述
Once there was a king called XOR, he had a lot of land. Because of his name, he likes to play XOR games.
One day, he whimpered and wanted to establish N cities on that vast expanse of land, numbered 0, 1, 2..., N-1. He wanted to connect all the cities. If city A can reach City B through zero or one or several cities, then A and B are connected. The cost of repairing a road in City A and City B is the XOR value of number of City A and number of City B. This King XOR wanted to figure out the minimum cost for connecting all of the N cities.
Of course, like a fairy tale read as a child, there will be corresponding rewards after helping the king. If you help the king solve his problems, he will improve your ranking in the competition.
输入描述:
There are multi test cases
each test cases contains an integer N (2 ≤N≤ 20000), the number of cities the king wants to establish.
输出描述:
For each test case, print the minimum cost for connecting all of the N cities in one line.
输入例子:
4
输出例子:
4
-->
输入
4
输出
4
说明
The weightof the minimum cost is 1+2+1=4 In the Sample Example.
题目的原意应该是求一个最小生成树。两点之间的权值就是点编号的异或值。
直接按题目意思来肯定是不行的，建不了这么大的图。。
然后按照最小生成树的思想想一下就会发现，由于两点之间的权值是固定的，那么n个点得到最小生成树的结果其实就是在n-1个点的基础上加上n-1这个点连接0~n-2中的最小权值，由于连接的点都比n-1小，那么与n-1异或值最小的m，应满足 其二进制中除开n-1的二进制数中最后一个1的位置不同，其他位都相同。
毕竟异或是相同就为0，不同就为1。
emmmm 然后就直接打表处理~~
// Asimple
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<" = "<<a<<endl
using namespace std;
typedef long long ll;
const int maxn = + ;
ll T, n, sum, num, m, t, len, ans;
ll fa[maxn]; ll qpow(ll n) {
ll ans = ;
ll a = ;
while( n ) {
if( n& ) ans *= a;
a = a*a;
n >>= ;
}
return ans;
} ll count(ll n) {
ll ans = ;
while( n% == ) {
n /= ;
ans ++;
}
return ans;
} void init() {
fa[] = ;
for(int i=; i<maxn; i++) {
fa[i] = fa[i-] + qpow(count(i-));
}
} void input() {
init();
while( ~scanf("%d", &n) ){
cout << fa[n] << endl;
} } int main() {
input();
return ;
}