これも何とか自力で解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=11395
問題
整数の集合S1,S2に対し、S2がS1の積であるとは、S2中にS1の各要素の倍数が含まれていることをいう。
ここで、SをA<=x<=B、C<=x<=Dを満たす整数xからなる集合とする。
Sの部分集合であり、かつSの積である集合のうち最小の要素数を求めよ。
解法
求める集合に2以上の整数kに対しk*xが含まれるなら、xは含める必要がない。
A<=B/2の場合、A~B/2の2倍はB以下なので、これらの数字は求める集合には含まれない。
同様に、C<=D/2の場合、C~D/2は求める集合に含まれない。
よってまずA=max(A,B/2+1)、C=max(C,D/2+1)で置き換える。
C~Dの各要素の比は2倍未満なので、これらの数値は答えの集合に含まれる。
後は整数kに対しC/k~D/kに相当する部分をA~Bの区間から取り除いていけばよい。
class SetMultiples { public: long long smallestSubset(long long A, long long B, long long C, long long D) { A=max(A,B/2+1); C=max(C,D/2+1); ll ret=D-C+1; while(A<=B) { if(D/A<2) { ret += B-A+1; break; } ll m=(C+(A-1))/A; if(m*A>D) { // out ll y=min(B+1,(C+(m-2))/(m-1)); ret+=y-A; A=y; } else { A=min(B+1,D/m+1); } } return ret; } };
まとめ
これは割とすんなり解法が思いついたけど、微妙な数値合わせに手こずった。