個の素数を用いてと素因数分解します．
買い物が終了したあとがで割り切れるための条件は，各に対して， がで割り切れることと同値です．
これはどの素因数を持つ整数をすでに購入しているかという状態に持つbitDPにより求めることができます．
時間計算量はを素因数分解したときの素因数の個数をとして です．小さい方から番目の素数をと表すことにする(つまり，)とおくと， より，の素因数の個数は高々個であることがわかるため この制約下でこの解法は十分高速に動作します．
