CodeForces 959 E Mahmoud and Ehab and the xor-MST(异或 思维)

本文主要是介绍CodeForces 959 E Mahmoud and Ehab and the xor-MST(异或 思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Ehab is interested in the bitwise-xor operation and the special graphs. Mahmoud gave him a problem that combines both. He has a complete graph consisting of n vertices numbered from 0 to n - 1. For all 0 ≤ u < v < n, vertex u and vertex v are connected with an undirected edge that has weight (where is the bitwise-xor operation). Can you find the weight of the minimum spanning tree of that graph?

You can read about complete graphs in https://en.wikipedia.org/wiki/Complete_graph

You can read about the minimum spanning tree in https://en.wikipedia.org/wiki/Minimum_spanning_tree

The weight of the minimum spanning tree is the sum of the weights on the edges included in it.

Input

The only line contains an integer n (2 ≤ n ≤ 1012), the number of vertices in the graph.

Output

The only line contains an integer x, the weight of the graph’s minimum spanning tree.

Example

input
4
output
4

题目大意

一个完全图，每两个点之间的权值是两个节点编号相异或的值，求最小生成树.

解题思路

代码实现

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);\
cin.tie(0);\
cout.tie(0);
typedef long long ll;
int main()
{IO;ll n;cin>>n;ll t=2,ans=0;while(n/t){ll x=(t/2-1);ans+=((n+x)/t)*(t/2);t*=2;}t/=2;if(n%t!=0)ans+=(t&(-t));cout<<ans<<endl;return 0;
}

这篇关于CodeForces 959 E Mahmoud and Ehab and the xor-MST(异或 思维)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---