SRM 547 DIV2 Hard: RelativelyPrimeSubset

解法

Sの要素が100以下と小さいので100以下の素因数でビットDPを試みたい。しかし、100以下の素数の個数は25個なので

2^25 * |S| <= 2^25*50 = 1.6777216 × 10^9

で間に合わない。

ここでたかだか25個の素数を列挙してみると

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

このうち53,59,61,67,71,73,79,83,89,97の10個の素数については

53*2>100より

Sの要素xが53以上の素因数をもつとき、xは素数。

よって53以上の素数は別個にカウントすれば良い。

25-10 = 15個の素数についてビットDPすれば

2^15*|S| <= 2^15 * 50 = 1638400

で間に合う。