Дорогие Программисты. Многие из вас возможно слышали задачу про лампочки, и , наверное, её решили.
Мне очень нужна ваша помощь в решении похожей задачи. А вот и она: http://www.e-olimp.com/problems/1906.
Может кто нибудь знает как её решать?
Дорогие Программисты. Многие из вас возможно слышали задачу про лампочки, и , наверное, её решили.
Мне очень нужна ваша помощь в решении похожей задачи. А вот и она: http://www.e-olimp.com/problems/1906.
Может кто нибудь знает как её решать?
Количество погашенных лампочек - количество чисел, у которых нечетное число делителей. Пусть a1, a2, ... , ak - степени в разложении на простые. Тогда у числа (a1 + 1) * (a2 + 1) * ... (ak + 1) делителей. Чтобы это число было нечетным, все числа (ai + 1) , etc должны быть нечетными. Значит все ai - четные. То есть все они больше 2. То есть на это число не влияет то, включали ли лампочки в честь человека с номером большим корня из N
это была задача А.
Разбор ведет Ельдар Богданов (gojira)
http://webfile.ru/5432832