TopCoder SRM 505 Div1 Medium: SetMultiples
コード
public class SetMultiples { public long smallestSubset(long A, long B, long C, long D) { C = Math.max(C, D / 2 + 1); A = Math.max(A, B / 2 + 1); long ans = D - C + 1; ans += B - A + 1; while (A <= B) { long x = (long) Math.ceil((double) C / B); long Cx = (long) Math.ceil((double) C / x); long Dx = (long) Math.floor((double) D / x); // [A, B]の中で、x倍した時に[C, D]に含まれる整数の範囲 long deleteL = Math.min(Dx, B); long deleteR = Math.max(A, Cx); ans -= Math.max(0, deleteL - deleteR + 1); //Cx以上の整数は取り除かれたか、x倍しても[C, D]に含まれない B = Cx - 1; } return ans; } }