시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 0 | 0 | 0 | 0.000% |
Толик только что узнал, что на свете существует двоичная система счисления. Обрадованный этим, он записал в столбик двоичные формы чисел 1, 2, ..., $n$. Получились числа 1, 10, 11, 100, 101, 110, 111, ...
После этого он стер все написанные единицы и стал изучать расположение нулей. Он выбрал число $k$ и в каждой строке, идя слева направо, выделил красным цветом каждый $k$-ый ноль, начиная с первого. Таким образом, оказались выделенными нули с номерами $1, k + 1, 2k + 1, \ldots$ Например если $k = 2$, $n = 56$ то получились бы такие строки:
1 | 1 0 0 0 | 1 1 1 1 | 1 0 1 1 0 | 1 1 1 0 1 | 1 0 0 1 0 0 | 1 0 1 0 1 1 | 1 1 0 0 1 0 |
1 0 | 1 0 0 1 | 1 0 0 0 0 | 1 0 1 1 1 | 1 1 1 1 0 | 1 0 0 1 0 1 | 1 0 1 1 0 0 | 1 1 0 0 1 1 |
1 1 | 1 0 1 0 | 1 0 0 0 1 | 1 1 0 0 0 | 1 1 1 1 1 | 1 0 0 1 1 0 | 1 0 1 1 0 1 | 1 1 0 1 0 0 |
1 0 0 | 1 0 1 1 | 1 0 0 1 0 | 1 1 0 0 1 | 1 0 0 0 0 0 | 1 0 0 1 1 1 | 1 0 1 1 1 0 | 1 1 0 1 0 1 |
1 0 1 | 1 1 0 0 | 1 0 0 1 1 | 1 1 0 1 0 | 1 0 0 0 0 1 | 1 0 1 0 0 0 | 1 0 1 1 1 1 | 1 1 0 1 1 0 |
1 1 0 | 1 1 0 1 | 1 0 1 0 0 | 1 1 0 1 1 | 1 0 0 0 1 0 | 1 0 1 0 0 1 | 1 1 0 0 0 0 | 1 1 0 1 1 1 |
1 1 1 | 1 1 1 0 | 1 0 1 0 1 | 1 1 1 0 0 | 1 0 0 0 1 1 | 1 0 1 0 1 0 | 1 1 0 0 0 1 | 1 1 1 0 0 0 |
(красные нули выделены жирным шрифтом и подчеркнуты)
Теперь Толику интересно, сколько же ноликов он выделил. Помогите ему их посчитать.
Во входном файле содержатся числа $n$ и $k$ ($1 \le n < 2^{31}$, $1 \le k \le 30$).
Выходной файл должен содержать одно число --- количество красных нулей.
4 1
3
56 2
74