SRM 458 Div2 Hard ProductTriplet

minx≦x≦maxx，miny≦y≦maxy，minz≦z≦maxzを満たす整数の組
(x,y,z)の個数を求めよ。
ただし1≦minx,miny,minz,maxx,maxy,maxz≦1,000,000,000である。

数字が10億と大きいのでナイーブにループを回して数え上げる方法は取れない。
なんとか√10億（≒3万）くらいのループで数える方法を考える必要がある。
するとx≦yとなる組だけ数えてみるという発想に至る。

xを固定したとき、xy=zよりminz/x≦y≦maxz/xであるので、
条件を満たすようなyは
上限A=min(maxz/x,maxy),下限B=max(minz/x,miny)の間にあり
かつy≧xであるような整数である。

x≦yを仮定したので最悪でもxは1から3万まで調べればよい。
次にy≦xの場合を同様に数え、最後に2回数えたx=yの場合を引く。

class ProductTriplet {
	public:
	long long countTriplets(int minx, int maxx, int miny, int maxy, int minz, int maxz)
	{
		ll cnt=0;
		//x<=y
		cnt+=calc(minx,maxx,miny,maxy,minz,maxz);
		//x>=y
		cnt+=calc(miny,maxy,minx,maxx,minz,maxz);
		
		//x=yを二回数えたので一回引く
		int A=min(maxx,maxy),B=max(minx,miny);
		A=min(A,(int)sqrt(maxz));
		B=max(B,(int)ceil(sqrt(double(minz))));
		if(A>=B)cnt-=A-B+1;
		
		return cnt;
	}
	ll calc(int mx,int Mx,int my,int My,int mz,int Mz)
	{
		ll ret=0;
		int X=(int)sqrt(Mz);X=min(X,Mx);
		//x<=yのものを数えるので√Mzまで考えれば十分

		for(int x=mx;x<=X;x++)
		{
			int A=Mz/x;
			//今のxに対するyの上限
			int B=(int)ceil(double(mz)/x);
			//y下限
			
			A=min(A,My);
			B=max(B,max(x,my));
			//yの範囲に注意（miny,maxyの条件とx<=yの条件）
			
			if(A>=B)ret+=A-B+1;
			//yが存在したときだけ足す
		}
		return ret;
	}
}

（ヘッダ、マクロは省略。llはlong longにtypedefされている）
条件が３つかぶる＆下限は切り上げる必要がある等、本番ではまりうる細かい落とし穴が多いかも？