Задача №1769. Цветные нули
Толик только что узнал, что на свете существует двоичная система счисления. Обрадованный этим, он записал в столбик двоичные формы чисел 1, 2, …, \(n\). Получились числа 1, 10, 11, 100, 101, 110, 111, …
После этого он стер все написанные единицы и стал изучать расположение нулей. Он выбрал число \(k\) и в каждой строке, идя слева направо, выделил красным цветом каждый \(k\)-ый ноль, начиная с первого. Таким образом, оказались выделенными нули с номерами 1, \(k\) + 1, 2\(k\) + 1, … Например если \(k\) = 2, \(n\) = 56 то получились бы такие строки:
(красные нули выделены жирным шрифтом и подчеркнуты)
Теперь Толику интересно, сколько же ноликов он выделил. Помогите ему их посчитать.
Во входном файле содержатся числа \(n\) и \(k\) (1 ≤ \(n\) < \(2^{31}\), 1 ≤ \(k\) ≤ 30).
Выходной файл должен содержать одно число – количество красных нулей.
5 1
4
23 3
20