kmjp's blog

競技プログラミング参加記です

TopCoder SRM 505 Div1 Medium SetMultiples

これも何とか自力で解けた。
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;
	}
};

まとめ

これは割とすんなり解法が思いついたけど、微妙な数値合わせに手こずった。