くるのプログラミング記録

プログラミングの感想とか解説とか。

OUPC2020 G. Construction Set 解説

問題条件を下記のように[1]-[4]とします。
[1]. どの要素も{\displaystyle 6}で割ったあまりは{\displaystyle 1}でない
[2]. どの相異なる{\displaystyle 2}つの要素も、{\displaystyle 1}で割ったあまりは等しい
[3]. どの要素も約数の個数は{\displaystyle 4}個である
[4]. どの相異なる{\displaystyle 2}つの要素も、最大公約数は{\displaystyle 1}である

まず[1]の条件で禁止される数は全て排除しましょう。

次に[2]の条件より、{\displaystyle 6}で割ったあまり{\displaystyle 0,2,3,4,5}に関してあまりを決め打ちして全探索を行いましょう。

以下その前提ですすめます。

まず[3]の条件より、集合の要素は全て次のいずれかです。

・ある素数{\displaystyle p}の{\displaystyle 3}乗
・相異なる素数{\displaystyle p}と{\displaystyle q}に対して{\displaystyle pq}

ここで[4]の条件より、集合内のどの{\displaystyle 2}要素も同じ素因数を持たないことがわかります。

よってある素数{\displaystyle p}の{\displaystyle 3}乗に関しては貪欲に全て集合に加えて良いです。またここで含んだ素数{\displaystyle p}を持つ{\displaystyle pq}の形で書ける数に関してはこの時点で除外して問題ないです。

ここで{\displaystyle 5}以上の素数に関しては全て{\displaystyle p=6n+1}あるいは{\displaystyle p=6m-1}と書くことが出来ることを考慮して、場合分けを考えましょう。


・{\displaystyle 6}で割った余りが{\displaystyle 0}のとき

加えられる数は、{\displaystyle 6}のみです。
集合の最大サイズは高々{\displaystyle 1}です。


・{\displaystyle 6}で割った余りが{\displaystyle 2}のとき

加えられる数は、{\displaystyle 8}あるいは{\displaystyle 2p}(ここで{\displaystyle p}は{\displaystyle p=6n+1}の形で書ける素数)のみです
ここで{\displaystyle 8}と{\displaystyle 2q}は互いに素ではないので、集合の最大サイズは高々{\displaystyle 1}です。


・{\displaystyle 6}で割った余りが{\displaystyle 3}のとき

加えられる数は、{\displaystyle 27}あるいは{\displaystyle 3p}(ここで{\displaystyle p}は{\displaystyle p=6n+1}の形で書ける素数)あるいは{\displaystyle 3q}(ここで{\displaystyle q}は{\displaystyle q=6m-1}の形で書ける素数)のみです
ここで{\displaystyle 27,3p,3q}はそれぞれ互いに素ではないので、集合の最大サイズは高々{\displaystyle 1}です。


・{\displaystyle 6}で割った余りが{\displaystyle 4}のとき

加えられる数は、{\displaystyle 2q}(ここで{\displaystyle q}は{\displaystyle q=6m-1}の形で書ける素数)のみです
集合の最大サイズは高々{\displaystyle 1}です。


・{\displaystyle 6}で割った余りが5のとき

加えられる数は、{\displaystyle p^3}あるいは{\displaystyle pq}(ここで{\displaystyle p}は{\displaystyle p=6n+1}の形で書ける素数、{\displaystyle q}は{\displaystyle q=6m-1}の形で書ける素数)のみです
{\displaystyle pq}の形で書ける数{\displaystyle p_1q_1,p_2q_2}に関しては、{\displaystyle p_1 \neq p_2}かつ{\displaystyle q_1 \neq q_2}ならば、両方選択することが出来ます。
すなわち{\displaystyle pq}の形で書ける素数に関して、素数を頂点としたグラフを考え頂点{\displaystyle p}と頂点{\displaystyle q}に辺を張ると、この問題は辺の張られたグラフから最大マッチングを考える問題になります。
また上記のグラフは{\displaystyle 2}部グラフになるため、最大マッチングが簡単に求まります。


よってこの問題が解けました。
計算量は素因数分解の際に{\displaystyle O(N \sqrt{A_{max}})} 、 二部マッチングの際に{\displaystyle O(N^2)}必要で、全体で {\displaystyle O(N \sqrt{A_{max}}+N^2)}となります。
素因数分解の際にポラード・ロー法などを用いることで、計算量をもう少し良くした解法もあります。