Make It One(CFR519-F)
\(N\) 要素からなる数列 \(A\) がある。
この要素からいくつか選んでその \(\gcd\) を \(1\) とする時、選ぶ要素数は最小でいくつになるだろうか。また、そのように選ぶことが不可能な場合 \(-1\) を出力せよ。
\( 1 \le N,A_i \le 300000 \)
まず、 \(-1\) の判定は簡単で、「全要素の \(\gcd\) が \(1\) 以外」⇔「正しい選び方は存在しない」です。
では、どのように最小を求めるのでしょうか。
直感的に、この最小はそんなに大きくならないことは、素数の小さいほうから \(7\) つの積が \(A_i\) の制約を超える ( \(2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 = 510510 > 300000\) ) ことから分かると思います。
このことは、ざっくり以下の説明で示せます。
まず、ある数列の要素 \(A_i\) について、2つ以上同じ素因数を含む場合、それは1つとみなしてよい。なぜなら、いずれその素因数を含まない要素を選ぶことになるからである。
さらに、選ぶ要素を増やしていく段階で、 \(\gcd\) が小さくならないような選択は無意味であるので、 \(\gcd\) に含まれる素因数の(種類)数は(狭義)単調減少していくことになる。
この上で、予め数列を「素因数が \(p\) が \(A_i\) に含まれるなら、その数は必ず \(1\) つである」と圧縮しておきます。その方が (他の方針も検討するにあたって) 考えやすかったので。
この上で、「\(\gcd = 1\) である \(k\) 要素の集合が選べない」⇔「ありうる任意の \(k\) 要素の集合について、その要素らは何かしら約数を共有している」
という訳で、これらを「ある約数 \(d\) を共有している集合」という観点で捉えてみると、
「約数 \(2\) を共有している」、「約数 \(3\) を共有している」、その和集合は
「約数 \(6\) を共有している」…
ここで、これは数え上げられそうな形になっていることに気付きます。
結論から申し上げますと、これは包除原理を適用可能な形です。
数え上げるものを「何らかの約数を共有する \(k\) 要素の集合」、列挙していく条件を「約数として素数 \(p\) を共有している」ととると、特定の条件を \(c\) 個満たす集合が「異なる素数 \(c\) 個の積 \(P\) を、約数として共有している」、この場合の符号が \((-1)^{c-1}\) となって、このとき、\(300000\) 以下の \(P\) について当てはまる(圧縮後の) \(A\) の要素数は予計算可能です。
そして、実際にこれを要素数の少ない方から具体的に数え上げを行い、要素数 \(k\) を検討する際に圧縮後の要素数を \(m\) として結果が \(_mC_k\) となればその要素数ではどう選んでも \(\gcd=1\) と出来ないことになる、としても、包除原理の項数が \(300000\) かそれよりかなり小さいあたりかで、 \(k\) がそう大きくならないことから、この問題を解くに十分高速です。
しかし、ひとつ問題が残ります。「数えるべき集合の数 \(_mC_k\)」は、実はかなり大きくなります。余裕をもって見積もって \( _{300000}C_7 >> 10^{18} \) で、long longが余裕で死にます。ここで、求めたい事柄は「数え上げた総和と \(_mC_k\) が一致するかどうか」なので、適当に大きな \( mod \) を取ってやってハッシュして調べればよいです。不安なら、複数 \( mod \) なり乱択 \( mod \)なりお好きにどうぞ。筆者のコードでは \(6\) 種類 \(10^9\) 近辺の \( mod \) を取っても 200ms 程度で AC を確認しています。
Submission #102353672 - Codeforces
「最小値探索問題」を「数え上げの問題」に変換して解くという着想が個人的にかなり面白かったのでメモ。
