Task 75. Тумблеры
UniLecsЗадача: дано бесконечное число тумблеров (переключателей), ктр находятся в выключенном состоянии. На каждом шаге включаются (если они были выключены) или выключаются (если они были включены) все те тумблеры, номера которых (нумерация с 1) кратны номеру шага.
Нужно определить состояние N-й лампочки после N-го шага.
Входные данные: N - номера шага, где N - натуральное число, N <= 10^5.
Вывод: вывести состояние тумблера после N-го шага.
Пример:
1. N = 1, Status = 1
2. N = 5, Status = 0
Идея: рассмотрим частный случай: пятый тумблер поменяет свое состояние на первом и пятом шаге (так как 5 делится только на 1 и 5). Поскольку изначально он был выключен, то после 5-го шага он также будет выключенным:
- Если N имеет четное число делителей, то после N-го шага тумблер снова будет выключенным.
- И наооборот, если N имеет нечетное количество делителей, то после N-го шага тумблер будет включенным.
Случай нечетного кол-ва делителей возможен только если N является полным квадратом.
Если число является полным квадратом, то все его простые делители входят в его разложение на простые множители с четными степенями.
Если N = p1^a1 * p2^a2 *...*pk^ak, то его число делителей равно:
D(N) = (a1 + 1)*(a2 + 1)*...*(ak + 1)
Если N - полный квадрат, то все ai четны. А значение D(N) нечетно, т.к. является произведением нечетных чисел.
Более подробно про разложение числа на простые множители и определение кол-ва делителей вы можете почитать на WikiHow.
Реализация:
https://gist.github.com/unilecs/b9188b8404f105bf9ba4e6f369a9235d
Тест: