Эхаб интересуется побитовым исключающим ИЛИ и особыми графами, поэтому Махмуд предложил ему задачу про оба его интереса сразу. У Махмуда есть полный граф, состоящий из 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 — вес минимального остовного дерева данного графа.
В первом примере: Вес минимального остовного дерева равен 1+2+1=4.
4
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач
Вес минимального остовного дерева равен 1+2+1=4.