整数 $n$ が与えられる。以下の問題を解け。
各要素が $1 \le a_i \le n$ であり、かつ要素に重複が無い数列 $a$ を考える。
このとき、この数列 $a$ はある整数 $ m $ について
$\displaystyle \prod_{i=1}^{|a|}(a_i!) = m^2$ を満たしたという。
数列 $a$ として考えられる最長のものをひとつ求めよ。
$1 \le n \le 10^6$
この問題を解く最大のカギは、「答えとなる数列の長さは、少なくとも $n-3$ である」という点ですが、かなり直感的に受け入れ難かったので、証明をメモ。 このコメント の証明を追っていきます。
まず、 $f(x)=$ ($x$ に奇数個だけ含まれる素因数の総積) と定めます。
このとき、 $f(x^2 y)=f(y)$ という性質が成り立つのが嬉しいポイントです。
これより、任意の正整数 $z$ に対して $f(z! \times (z+1)!) = f(z! \times z! \times (z+1)) = f(z+1)$ という性質も成り立ちます。( $x$ が偶数だった場合に $x \oplus (x+1)=1$ が成り立つのにどことなく近い気がします)
以下、 $n$ は十分大きいものとします。
まず、 $n$ が偶数の場合。 ($2k=n$ とおきます)
$f(1! \times 2! \times \dots \times (2k-1)! \times 2k!) = f(2 \times 4 \times \dots \times k) = f(2^l \times k!)$ ($l \in \{0,1\}$) となります。
これを考えると、 $S=\{1,2,...,n\}$ から $k$ と必要に応じて $2$ を抜いたり入れたりした集合が解となります。これにより、サイズ $n-2$ 以上の解が構築されました。
ここまで来れば $n$ が奇数の場合は簡単で、 $n-1$ の場合でサイズ $n-3$ 以上の解を構築すればよいです。
では、サイズ $n-2$ 以上の解はどのように探索すればよいか？
勘のいい方は「平方数であるものを求めよ」の枕詞で気づくかもしれませんが、「(素因数の)集合と集合の比較」という問題を解くことになるのと、「要素の個数のパリティだけが重要」という $2$ 点から、 $\mathrm{XOR}$ でハッシュしてやればよいです。
サイズ $n$ の解は $S$ を判定すればよく、 $n-1$ の解は $S$ から各要素を消したらどうなるかの $O(n)$ 、 $n-2$ の解も ( $S$ の全体のハッシュ値) $\oplus$ (ある要素のハッシュ値) というハッシュ値をもつ要素が選べるかどうかみたいな判定問題を解けば $O(n)$ です。説明が適当なので詳しくは実装を見てください。
