Эффективный двигатель

Автор задачи и разработчик: Мария Жогова

Докажем, что в конце будут активными только те карманные вселенные, которые являются полными квадратами. Посмотрим на произвольное число $$$m$$$ и на его разложение на простые: $$$$$$m = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k}\text{.}$$$$$$

Известно количество его натуральных делителей, оно равно в точности $$$(a_1 + 1) \cdot (a_2 + 1) \cdot \ldots \cdot (a_k + 1)$$$. Действительно, каждое простое из разложения $$$m$$$ входит в его делитель независимо от других со степенью от $$$0$$$ до соответствующего $$$a_i$$$ включительно.

Заметим, что такое произведение нечетно тогда и только тогда, когда все $$$a_i$$$ четны. А это равносильно тому, что $$$\sqrt{m}$$$ — целое число, то есть $$$m$$$ — полный квадрат. А если карманная вселенная номер $$$m$$$ активна, это как раз и равносильно тому, что количество делителей $$$m$$$ нечетно, ведь изначально все вселенные заморожены, а дальше меняют свое состояние перед каждым полетом, номер которого является делителем $$$m$$$.

Посчитать количество полных квадратов от $$$1$$$ до $$$n$$$ можно за время $$$\mathcal{O}(1)$$$, просто вычислив корень из $$$n$$$ и округлив его вниз.