eolymp
bolt
Try our new interface for solving problems
Məsələlər

Подсчет единиц

Подсчет единиц

Карл --- самый счастливый ребенок в мире: он сегодня утром узнал, что такое двоичная система счисления. Он например узнал, что бинарное представление положительного числа $k$ есть строка $a_na_{n-1} ... a_1a_0$, где каждое $a_i$ --- цифра $0$ или $1$, начиная с $a_n = 1$, при этом \includegraphics{https://static.e-olymp.com/content/7f/7fb1dbe815ab106463567468a6b41ada392bd6bc.jpg} Очень интересно наблюдать превращение десятичных чисел в двоичные, а также складывать и умножать их. Цезарь --- старший брат Карла, и он не может просто так стоять и наблюдать за счастьем брата. Поэтому он приготовил задачу: "Посмотри, Карл, у меня есть к тебе вопрос: Я дам тебе два целых числа $a$ и $b$, а ты скажешь мне сколько $1$-ц в бинарном представлении всех чисел от $a$ до $b$ включительно. Приготовься". Карл согласился принять вызов. Через несколько минут он вернулся со списком двоичных представлений всех чисел от $1$ до $100$. "Цезарь, я готов". Цезарь улыбнулся и сказал: "Хорошо, я выберу $a = 10^{15}$ и $b = 10^{16}$. Твой список бесполезен". Карл не хочет проиграть брату, ему необходимо быстрое решение. Можете ли ему помочь? \InputFile В одной строке расположены два целых числа $a$ и $b~(1 \le a \le b \le 10^{16})$. \OutputFile Выведите общее количество цифр $1$ в двоичном представлении всех целых чисел от $a$ до $b$ включительно.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
2 12
Çıxış verilənləri #1
21
Müəllif Ray Williams Robinson Valiente
Mənbə 2013 ACM Regional Latino America, Задача C