Задачи на собеседовании в одну небезызвестную контору

[CDR]

Цитата:

Сообщение от kashperuk

Про лампочки на самом деле все довольно просто
1ая будет включена - ее только один раз включили, в самом начале.
2ая будет выключена - ее при первом обходе включили, при втором выключили
3ья будет выключена - ее при первом обходе включили, при третьем выключили
4ая будет включена - ее при первом обходе включили, при втором выключили, при 4ом включили.
и так дальше. видим, что включены получаются только те, для которых кол-во включений/выключений было нечетным.

А это действительно только для тех, которые являются квадратом какого-то числа (они будут включаться/выключаться парное кол-во раз + 1 (первый проход))

Правильно!
Как было тонко подмечено, состояние лампочки зависит от четного или нечетного количества ее переключений. Четность/нечетность количества переключений в свою очередь определяется количеством делителей для числа, являющегося порядковым номером лампочки. Если количество делителей четное - лампочка будет выключена, в противном случае - включена.
Для каждого делителя числа существует симметричный ему делитель, получающийся от деления числа на этот делитель. Другими словами, если число N делится без остатка на D, то это же число N делится без остатка и на частное от этого деления. Единственный делитель, который не имеет симметричного "отражения", является корнем (или квадратом ) числа.

Соответственно лампочки, являющиеся квадратами чисел 1, 2, 3, 4, 5, 6, 7, 8, 9 и 10 будут включены, все остальные выключены