A,B,C問題はやるだけだった。D問題について、エラトステネスの篩をつかってなんかできそうと思ったがそもそもアルゴリズムとその計算量を忘れかけていて時間がかかった。問題は、N個の整数が与えられていてそのどれともgcd(A[i],k)=1となるようなkをすべて列挙せよ、というものだ。それぞれ素因数分解したら間に合わなそうだから、エラトステネスで素数判定する中でA[i]に入るかも判定しようとしたがどうも計算量とそのアルゴリズムがはっきりしなくて時間がかかってしまった。ここまで３０分。
E問題は、bitdpだな－とは思いつつもなかなかちゃんとしたdpを組めなかった。
dp[i][S][j]と３次元にしてしまうと計算量がきつくなりそうでずっと２次元で行ける方法を探していたが、結局見つからず残り１５分程度で３次元dpを書くことに踏み切った。
遷移を考えたら思ったよりシンプルで計算量は多くてO(10^7)だった。
