問題概要
長さ $N$ の数列 $A$ が与えられる。
以下の条件を満たす $1,2$ からなる長さ $N$ の数列 $B$ があるか判定し、あるならひとつ構築せよ。
- $B_i=1$ なる $i$ を並べた数列を $X$ とする。このとき、 $\gcd(A_{X_1},A_{X_2},\dots)=1$ である。
- $B_i=2$ なる $i$ を並べた数列を $Y$ とする。このとき、 $\gcd(A_{Y_1},A_{Y_2},\dots)=1$ である。
$2 \le N \le 10^5$
$1 \le A_i \le 10^9$
要は $A$ をふたつに分けてそれぞれの $\gcd$ を $1$ にせよというもの。
$N \le 18$ 程度なら bit 全探索可能なのでそうする。
さらに、 $A_i \le 10^9$ より $A_i$ は相異なる素因数を高々 $9$ 種類しか含まないことが分かる。
漠然としすぎているので $1$ 側に含まれる要素を $1$ つ固定したとする。
ここでひとつ分かることがある。
$\gcd$ を取る過程で相異なる素因数の種類数をどんどん減らしていくことになるが、この時「素因数 $\alpha$ を消すために追加する要素 $A_i$ 」「素因数 $\beta$ を消すために追加する要素 $A_j$ 」... という感じで要素を追加しない限り、要素の追加は無駄であることが分かる。すなわち何が言いたいかというと、「ある解について、 $1$ 側に含まれる要素の個数を高々 $9$ 個とできる」ということが分かる。
ここで、大胆にも $2$ 側に含まれる要素も ランダムで $1$ つ固定したとする。
このとき、先ほどの「ある解」に含まれている要素を間違えて $2$ 側に含んでしまう確率は高々 $\frac{9}{N-1}$ であることが分かる。
では、 $\frac{N-10}{N-1}$ 以上の確率で生き残っている「ある解」を掘り起こすことを考えよう。
まず、 $dp[$ ( $1$ 側の素因数のうち残っているものの集合) ( $2$ 側の素因数のうち残っているものの集合) $]$ のようなことをすれば $O(2^{18}N)$ で解けるだろう。
このままでは非常に重いですが、「ある素因数 $p$ が含まれない」ような要素は $p$ それぞれについて高々 $18$ 個しか調べる必要がないことが分かります。何故なら、 $19$ 個目を追加するタイミングではもう $p$ を折る意味はなくなっているからです。(無駄にならない要素の追加は高々 $18$ 回なので、同じ素因数について $19$ 個目を入れておく意味がない)
これにより $O(2^{18}18^2)$ 程度の計算量で残りの問題が決定的に解けました。
これを $T$ 回回せば通る確率は $1 - \left ( \frac{1}{2} \right ) ^{T}$ 以上となり、時間いっぱい回せば $T \ge 10$ くらいにはなるのでこの問題に十分高い確率で正解できます。( $N$ が大きいほど bitDP の計算量がやや膨らみますが成功確率が上がるので、ちゃんと計算すればもうちょっと良い見積もりを得ます)
Submission #204169550 - Codeforces
決め打ち $1$ 回ごとの乱択の成功確率の見積もりが非常に美しい。
