from ABC195 ABC195F
- 考えたこと
- 素因数分解して、素因数にオーバーラップがないように選ぶ
- 72個あるので2^72通り
- 包除原理？
- 余事象を考える？
- 数え上げテクニック集
- 素因数と数との二部グラフにしたら、やることは二部マッチングを求めることといえる
- 最大な一つを求めるのではなく、数え上げなのでこのやり方では無さそう
- 素因数があるかないかをビットにしてbitDP？
- 2^72では大きすぎる
- 72って特殊な制約だな
- 連続する整数なので73以上の素因数は2回出現できない
- 72以下の素数に関してだけ考えれば良い
- 72以下の素数は20個、これでいける？
- 公式解説「この解法は十分高速です」
-
COLOCON2018Cの難しい版 tw