Another Game With Numbers (SPOJ 6285)

http://www.spoj.pl/problems/NGM2/

問題

1〜Nまでの数字がある。1〜Nまでの数字でxの約数になっている物を取り除くという操作をk回行う。最後に残っている数字は何個かという問題。
N<=10^9,k<=15,x<=100

解法

kが小さいので全ての組み合わせに対して包含原理を使って計算すれば良い。