TopCoder SRM 505 Div1 Medium: SetMultiples
問題
自然数の集合 S1 と S2 がある。S1 に含まれる全ての数について、その数の自然数倍の数が S2 に含まれるとき、S2 は S1 の multiple であるということにする。
S に含まれる自然数 x は A<=x<=B あるいは C<=x<=D を満たす。S の部分集合であり、かつ、S の multiple である集合の中で最小の要素数はいくつか。
解法
まず A<=x<=B や C<=x<=D の中で multiple になっている場合はそれを削る。
A = Math.max(A, B / 2 + 1); C = Math.max(C, D / 2 + 1);
[C, D] 側は削れないので、[A, B] の数のうち、自然数倍が [C, D] に含まれるものを削除することを考える。
コード
public class SetMultiples { public long smallestSubset(long A, long B, long C, long D) { A = Math.max(A, B / 2 + 1); C = Math.max(C, D / 2 + 1); long answer = D - C + 1 + B - A + 1; while (true) { //k*B>=C long k = (C + B - 1) / B; long a = (C + k - 1) / k; a = Math.max(a, A); long b = D / k; b = Math.min(b, B); long rid = b - a + 1;//[a, b] rid = Math.max(rid, 0); answer -= rid; //いまは a*k が [C, D] に入っている B = a - 1; if (A > B) return answer; } } }