Подразделы

Другие разделы

09/04/2025 19:00:34

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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

Пример ввода 2

56 2

Пример вывода 2

Источник: XII командный чемпионат школьников Санкт-Петербурга по программированию.