Can you Divide?

$m$個の素数を用いて$d=p_1 \times p_2 \times \cdots \times p_m$と素因数分解します．

買い物が終了したあと$x$が$d$で割り切れるための条件は，各$p_i(1 \leq i \leq m)$に対して， $x$が$p_i$で割り切れることと同値です．

これはどの素因数を持つ整数をすでに購入しているかという状態に持つbitDPにより求めることができます．

時間計算量は$d$を素因数分解したときの素因数の個数を$m$として $O(\sqrt{d} + 2^m \times N)$です．小さい方から$i$番目の素数を$P_i$と表すことにする(つまり，$P_1=2,P_2=3,P_3=5\cdots$)とおくと， $P_1 \times P_2 \times \cdots \times P_{10} = 8700621930 \geq 10^9$より，$d$の素因数の個数は高々$10$個であることがわかるため この制約下でこの解法は十分高速に動作します．