eolymp
Yarışlar

October 7 - BMTK Programming School, High League

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

Карл - самый счастливый ребенок в мире: он сегодня утром узнал, что такое двоичная система счисления. Он например узнал, что бинарное представление положительного числа k есть строка anan-1...a1a0, где каждое ai - цифра 0 или 1, начиная с an = 1, при этом prb6583. Очень интересно наблюдать превращение десятичных чисел в двоичные, а также складывать и умножать их.

Цезарь - старший брат Карла, и он не может просто так стоять и наблюдать за счастьем брата. Поэтому он приготовил задачу: "Посмотри, Карл, у меня есть к тебе вопрос: Я дам тебе два целых числа a и b, а ты скажешь мне сколько 1-иц в бинарном представлении всех чисел от a до b включительно. Приготовься". Карл согласился принять вызов. Через несколько минут он вернулся со списком двоичных представлений всех чисел от 1 до 100. "Цезарь, я готов". Цезарь улыбнулся и сказал: "Хорошо, я выберу a = 1015 и b = 1016. Твой список бесполезен".

Карл не хочет проиграть брату, ему необходимо быстрое решение. Можете ли ему помочь?

Входные данные

В одной строке расположены два целых числа a и b (1a b 1016).

Выходные данные

Вывести общее количество цифр 1 в двоичном представлении всех целых чисел от a до b включительно.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 122.17 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