| Codeforces Round 473 (Div. 2) |
|---|
| Закончено |
Эхаб интересуется побитовым исключающим ИЛИ и особыми графами, поэтому Махмуд предложил ему задачу про оба его интереса сразу. У Махмуда есть полный граф, состоящий из n вершин, пронумерованных с 0 до n - 1. Для любых 0 ≤ u < v < n, вес ненаправленного ребра между вершинами u и v равен 
(где 
— операция побитового исключающего ИЛИ). Можете ли вы найти вес минимального остовного дерева данного графа?
Прочитать про полные графы можно в https://ru.wikipedia.org/wiki/Полный_граф.
Прочитать про минимальное остовное дерево можно в https://ru.wikipedia.org/wiki/Минимальное_остовное_дерево.
Вес минимального остовного дерева равен весу всех рёбер, включённых в него.
В единственной строке содержится одно целое число n (2 ≤ n ≤ 1012) — число вершин в графе.
В единственной строке содержится одно целое число x — вес минимального остовного дерева данного графа.
4
4
В первом примере: 
Вес минимального остовного дерева равен 1+2+1=4.
