| Автор: | XII Командный чемпионат школьников Санкт-Петербурга по программированию | Ограничение времени: | 2 сек | |
| Входной файл: | zeroes.in | Ограничение памяти: | 8 Мб | |
| Выходной файл: | zeroes.out |
Толик только что узнал, что на свете существует двоичная система счисления. Обрадованный этим, он записал в столбик двоичные формы чисел 1, 2,…, n. Получились числа 1, 10, 11, 100, 101, 110, 111, …
После этого он стер все написанные единицы и стал изучать расположение нулей. Он выбрал число k и в каждой строке, идя слева направо, выделил красным цветом каждый k-ый ноль, начиная с первого. Таким образом, оказались выделенными нули с номерами 1, k + 1, 2 k + 1, … Например если 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 |
Теперь Толику интересно, сколько же ноликов он выделил. Помогите ему их посчитать.
| № | Входной файл (zeroes.in) |
Выходной файл (zeroes.out) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|