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

TopCoder SRM 505 Div1 Medium: SetMultiples

解法

d.hatena.ne.jp

[C, D]の中でC*2<=DならCを上げて良い。

コード

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