読者です 読者をやめる 読者になる 読者になる

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;
    }
  }
}