Ctrl K

Доска с остатком один

Лёгкая
На доске написано одно число start. Каждый раунд происходит следующее: для каждого числа x, уже написанного на доске, находят все числа i от 1 до start, для которых x % i == 1, и дописывают их на доску. Числа с доски никогда не стираются, одинаковые числа повторно не пишут. Раундов проходит миллиард. Сколько различных чисел окажется на доске в конце?
Пример 1
start=6 → 5

6 даёт остаток 1 при делении на 5 — пишем 5. 5 даёт остаток 1 при делении на 2 и 4. 4 даёт остаток 1 при делении на 3. На доске 6, 5, 4, 3, 2 — пять чисел.

Пример 2
start=2 → 1

Для 2 подходящих делителей нет (2 % 1 = 0, 2 % 2 = 0), на доске так и остаётся одно число.

Ограничения
  • 1 ≤ start ≤ 100
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПотерянный билет ЛёгкаяРовные стопки карт ЛёгкаяНечётные счётчики после нажатий ЛёгкаяЧем кончилась партия в крестики-нолики ЛёгкаяПары равных элементов Лёгкая
загружаем Python…
Вход
start=6
Ожидается
5

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 52 теста на сервере, включая скрытые.