TopCoder SRM 505 Div1 Medium SetMultiples

問題

整数を要素とする二つの集合S1,S2があったとき、
S2がS1の倍数であるとは、S1のどんな要素xに対しても、
ある整数kおよびS2の要素yが存在して、y=x*kが成り立つことを言う。

Sを、A<=x<=BまたはC<=x<=Dを満たす整数の集合とする。
Sの倍数であるような集合のうち、要素の数が最小であるようなものの、要素の個数を求めよ。

制約条件

A,B,C,D≦10^10

方針

区間[C,D]のうち、D/2以下の整数は、その倍数が[D/2+1,D]に含まれているため、
C=max(C,D/2+1)としてよい。
同様に、A=max(A,B/2+1)としてよい。

区間[A,B]から、[C,D]にその倍数を持つ数を削っていく。
B以下の最も大きい数になるようCをある整数kで割る。
これはC/k≦B⇔C/B≦kより、C/Bを切り上げた数をkとすればよい。

C/k（を切り上げた整数）以上D/k以下の整数については、区間[C,D]に倍数となる整数が存在するため、消すことができる。

B=C/k（を切り上げた整数）-1として、以上のプロセスを更新がなくなるまで続ければよい。

ソースコード

class SetMultiples {
	public:
	long long smallestSubset(long long A, long long B, long long C, long long D) 
	{
		C=max(C,D/2+1);
		A=max(A,B/2+1);
		ll ans=D-C+1+B-A+1;
		while(A<=B){
			ll k=(C+B-1)/B;
			ll s=(C+k-1)/k, t=D/k;
			ans-=max(0ll,min(B,t)-max(A,s)+1);
			B=s-1;
		}
		return ans;
	}
};