Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
261. Цветные нули
Олимпиадные задачи на русском языке| 20/07/2007 | Лето 2007 - 9 (задачи XII СПб командного чемпионата школьников) (I) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Толик только что узнал, что на свете существует двоичная система счисления.
Обрадованный этим, он записал в столбик двоичные формы чисел 1, 2, …, `n`.
Получились числа 1, 10, 11, 100, 101, 110, 111, …
После этого он стер все написанные единицы и стал изучать расположение
нулей. Он выбрал число `k` и в каждой строке, идя слева направо, выделил красным цветом каждый
`k`-ый ноль, начиная с первого. Таким образом, оказались выделенными нули с номерами
`1,\ k\ +\ 1,\ 2k\ +\ 1,\ …` Например, если `k\ =\ 2`, `n\ =\ 56`, то получились бы такие строки:
Теперь Толику интересно, сколько же ноликов он выделил.
Помогите ему их посчитать.
Ввод
Во входном файле содержатся числа `n` и `k` (`1\ ≤\ n\ <\ 2^{31}`, `1\ ≤\ k\ ≤\ 30`).
Вывод
Выходной файл должен содержать одно число — количество красных нулей.
Пример ввода 1
4 1
Пример вывода 1
3
Пример ввода 2
56 2
Пример вывода 2
74
