Начало
Лето 9
A. Катание на автобусах B. Старая крепость C. Гистограмма D. Два коня E. Сапер F. Интересное число G. Треугольник Паскаля H. Два прямоугольника I. Цветные нули
I. Цветные нули
Олимпиадные задачи на русском языке| 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
