二次集合 (Quadratic Set, CF1622F)

给你一个正整数\(n(1\leq n\leq 10^6)\). 你需要从集合\(\{1,2,...,n\}\)中选\(k\)个元素(每个元素至多选一次)组成数列\(a_1,a_2,...,a_k\), 使得\(\prod\limits_{i=1}^{k}a_i!\)是完全平方数. 你希望\(k\)尽可能大. 输出\(k\)的最大值, 并输出此时选出的\(k\)个元素.

[分析]

如果\(n\)是偶数, 那么\(\prod\limits_{i=1}^ni!=\prod\limits_{i=1}^{\frac{n}{2}}((2i-1)!)^2\cdot2i=2^{\frac{n}{2}}(\frac{n}{2})!\prod\limits_{i=1}^{\frac{n}{2}}((2i-1)!)^2\)

因此若\(\frac{n}{2}\)为偶数, 则在所有阶乘中去掉\((\frac{n}{2})!\)即可. 若\(\frac{n}{2}\)是奇数, 则去掉\(2!\)和\((\frac{n}{2})!\)即可. 如果\(n\)是奇数, 那么\(n-1\)是偶数. 因此去掉\(n!\)即转化为偶数的情况. 即: 如果\(\frac{n-1}{2}\)是偶数, 则去掉\(n!\)和\((\frac{n-1}{2})!\)即可, 如果\(\frac{n-1}{2}\)是奇数, 则去掉\(n!\)和\((\frac{n-1}{2})!\)和\(2!\)即可. 总之, 至少在\(\{1,2,...,n\}\)可以选择\(n-3\)个元素满足题意.

接下来考虑如何验证\(k\)是否能够等于\(n\)或\(n-1\)或\(n-2\). 为此我们采用\(hash\)技术, 为每个素数设置一个\(hash\)值. 于是每个整数的\(hash\)函数就是它的所有素因子(按重数计算)的\(hash\)值的异或和. 设\(H(u)\)为\(u\)的\(hash\)值. 那么我们可以算出\(H(1!),H(2!),...,H(n!)\), 进而算出\(H(1!\cdot2!\cdot ...\cdot n!)\)(利用\(H(ab)=H(a)\ xor\ H(b)\)). 于是可以依次进行如下三类验证:

\(k=n\)当且仅当\(H(1!\cdot2!\cdot ...\cdot n!)=0\);

\(k=n-1\)当且仅当存在\(1\leq i\leq n\)满足\(H(1!\cdot2!\cdot ...\cdot n!)=H(i!)\), 直接验证即可;

\(k=n-2\)当且仅当存在\(1\leq i,j\leq n\)满足\(H(1!\cdot2!\cdot ...\cdot n!)\ xor\ H(i!)=H(j!)\), 利用\(unordered\_map\)即可完成搜索(若\(i=j\), 则落入\(k=n\)的情况).

总时间复杂度\(O(n)\).