Quadratic Set
Contest: Educational Codeforces Round 120 (Rated for Div. 2)
Difficulty rating: 2900
Tags: constructive algorithms, hashing, math, number theory

Let's call a set of positive integers $$$a_1, a_2, \dots, a_k$$$ quadratic if the product of the factorials of its elements is a square of an integer, i. e. $$$\prod\limits_{i=1}^{k} a_i! = m^2$$$, for some integer $$$m$$$.

You are given a positive integer $$$n$$$.

Your task is to find a quadratic subset of a set $$$1, 2, \dots, n$$$ of maximum size. If there are multiple answers, print any of them.

Input format:
A single line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

Output format:
In the first line, print a single integer — the size of the maximum subset. In the second line, print the subset itself in an arbitrary order.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
1

Example output:
1
1

Example input:
4

Example output:
3
1 3 4

Editorial:
A good start to solve the problem would be to check the answers for small values of $$$n$$$. One can see that the answers (the sizes of the maximum subsets) are not much different from $$$n$$$ itself, or rather not less than $$$n-3$$$. Let's try to prove that this is true for all $$$n$$$.
Consider $$$n$$$ is even. Let $$$n=2k$$$, let's see what the product is equal to if we take all the numbers from $$$1$$$ to $$$n$$$.
$$$\prod\limits_{i=1}^{2k} i! = \prod\limits_{i=1}^{k} (2i-1)! (2i)! = \prod\limits_{i=1}^{k} (2i-1)!^2 2i = (\prod\limits_{i=1}^{k} (2i-1)!)^2 \prod\limits_{i=1}^{k} 2i = (\prod\limits_{i=1}^{k} (2i-1)!)^2 2^k k!$$$
From here we can see that for even $$$k$$$ the answer is at least $$$n-1$$$, because we can delete $$$k!$$$ and the product of the remaining factorials will be the square of an integer, for odd $$$k$$$ the answer is at least $$$n-2$$$, because we can delete $$$2!$$$ and $$$k!$$$.
It remains to prove that the answer is at least $$$n-3$$$ for odd $$$n$$$. This is easy to do, because the answer for $$$n$$$ is not less than the answer for $$$n-1$$$ minus $$$1$$$, because we can delete $$$n!$$$ and solve the task with a smaller $$$n$$$ value. Moreover, it can be seen from the previous arguments that the answer $$$3$$$ can only be for $$$n \equiv 3 \pmod 4$$$, and we already know that in this case one of the correct answers is to remove the factorials $$$2, \frac{n-1}{2}, n$$$.
It remains to learn how to check whether it is possible to remove $$$1$$$ or $$$2$$$ numbers so that the remaining product of factorials is the square of an integer.
To do this, we can use XOR hashes. Let's assign each prime number a random $$$64$$$-bit number. For composite numbers, the hash is equal to the XOR of hashes of all its prime divisors from factorization. Thus, if some prime is included in the number an even number of times, it will not affect the value of the hash, which is what we need. The hash of the product of two numbers is equal to the XOR of the hashes of these numbers. Let's denote the hash function as $$$H$$$.
Using the above, let's calculate $$$H(i)$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$, as well as $$$H(i!)$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$, this is easy to do, because $$$H(i!) = H((i-1)!) \oplus H(i)$$$. We will also store a map $$$H(i!) \rightarrow i$$$. Let's calculate the hash $$$H(1!2! \cdots n!)$$$ and denote it as $$$fp$$$. It remains to consider the following cases:
• if $$$fp = 0$$$, then the current product is already the square of an integer;
• for an answer of size $$$n-1$$$, we have to check that there exists such a $$$i$$$ that $$$H(i!) \oplus fp = 0$$$. To find such $$$i$$$, let's check whether the map contains $$$fp$$$;
• for an answer of size $$$n-2$$$, we have to check that there are such $$$i$$$ and $$$j$$$ that $$$H(i!) \oplus H(j!) \oplus fp = 0$$$. To do this, iterate over $$$i$$$, and then check whether map contains $$$H(i!) \oplus fp$$$;
• otherwise, the answer is $$$n-3$$$, and there is an answer, where all numbers except $$$2, \frac{n-1}{2}, n$$$ are taken.