{"problem":{"name":"E. Mahmoud and Ehab and the xor-MST","description":{"content":"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. Fo","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF959E"},"statements":[{"statement_type":"Markdown","content":"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](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)). Can you find the weight of the minimum spanning tree of that graph?\n\nYou can read about complete graphs in [https://en.wikipedia.org/wiki/Complete_graph](https://en.wikipedia.org/wiki/Complete_graph)\n\nYou can read about the minimum spanning tree in [https://en.wikipedia.org/wiki/Minimum_spanning_tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree)\n\nThe weight of the minimum spanning tree is the sum of the weights on the edges included in it.\n\n## Input\n\nThe only line contains an integer _n_ (2 ≤ _n_ ≤ 1012), the number of vertices in the graph.\n\n## Output\n\nThe only line contains an integer _x_, the weight of the graph's minimum spanning tree.\n\n[samples]\n\n## Note\n\nIn the first sample: ![image](https://espresso.codeforces.com/4946726fa48431a5ac5abcbb96045299d81c25fe.png) The weight of the minimum spanning tree is 1+2+1=4.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"Ehab 对按位异或运算和特殊图感兴趣。Mahmoud 给了他一个结合了这两者的问题。他有一个包含 #cf_span[n] 个顶点的完全图，顶点编号从 #cf_span[0] 到 #cf_span[n - 1]。对于所有 #cf_span[0 ≤ u < v < n]，顶点 #cf_span[u] 和顶点 #cf_span[v] 通过一条无向边连接，该边的权重为 #cf_span[u \\oplus v]（其中 \\oplus 是按位异或运算）。你能找出该图的最小生成树的权重吗？\\n\\n你可以阅读有关完全图的信息：https://en.wikipedia.org/wiki/Complete_graph\\n\\n你可以阅读有关最小生成树的信息：https://en.wikipedia.org/wiki/Minimum_spanning_tree\\n\\n最小生成树的权重是其中包含的所有边的权重之和。\\n\\n输入仅包含一个整数 #cf_span[n] #cf_span[(2 ≤ n ≤ 10^{12})]，表示图中顶点的数量。\\n\\n输出仅包含一个整数 #cf_span[x]，表示该图最小生成树的权重。\\n\\n在第一个样例中：最小生成树的权重为 1+2+1=4。\"},{\"iden\":\"input\",\"content\":\"输入仅包含一个整数 #cf_span[n] #cf_span[(2 ≤ n ≤ 10^{12})]，表示图中顶点的数量。\"},{\"iden\":\"output\",\"content\":\"输出仅包含一个整数 #cf_span[x]，表示该图最小生成树的权重。\"},{\"iden\":\"note\",\"content\":\"在第一个样例中：最小生成树的权重为 1+2+1=4。\"}]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 10^{12} $.  \nConsider the complete graph $ G = (V, E) $ where:  \n- $ V = \\{0, 1, 2, \\dots, n-1\\} $,  \n- For every pair $ u, v \\in V $ with $ u < v $, there is an undirected edge $ (u, v) \\in E $ with weight $ u \\oplus v $, where $ \\oplus $ denotes bitwise XOR.\n\n**Objective**  \nCompute the total weight of the minimum spanning tree (MST) of $ G $.\n\n**Constraints**  \n$ 2 \\leq n \\leq 10^{12} $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF959E","tags":["bitmasks","dp","graphs","implementation","math"],"sample_group":[["4","4"]],"created_at":"2026-03-03 11:00:39"}}