欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

E. Mahmoud and Ehab and the xor-MST(神仙规律题)

程序员文章站 2023-12-26 23:58:57
...

http://codeforces.com/problemset/problem/959/E

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 E. Mahmoud and Ehab and the xor-MST(神仙规律题) (where E. Mahmoud and Ehab and the xor-MST(神仙规律题) 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

Copy

4

output

Copy

4

Note

In the first sample:E. Mahmoud and Ehab and the xor-MST(神仙规律题)The weight of the minimum spanning tree is 1+2+1=4.

我经历千辛万苦找的规律居然不能这样做。

A[n]=A[n-1]+pow(2,j)j是n-1数 二进制中最低位为1的位置。

但是n是1e12的,j又是变得无法用矩阵快速幂。

百度了一波题解,没太看懂,就先放着,感觉这类题还是比较难的对于我来说

来自:https://blog.csdn.net/elijahqi/article/details/79839261

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll n,ans,base=1;
int main(){
    freopen("cf959e.in","r",stdin);
    scanf("%lld",&n);
    while(n>1){
        ans+=base*(n>>1);base<<=1;n-=n>>1;
    }printf("%lld\n",ans);
    return 0;
}

 

上一篇:

下一篇: