BZOJ 2852: 强大的区间(辗转相除法)

Description

curimit很喜欢区间,最近发现了一种很强大的区间。
curimit发现有的区间虽小,比如 (1.99998, 2.000001),但是其中却包含了一个整数2。
但是有的区间较大,比如(1.0001, 1.99998),但是其中却一个整数都没有。
他觉得包含整数的区间很强大,并且提出了一个问题:
我们先给出两个非负实数a,b我们要求一个最小的正整数k ,使得区间(a*k, b*k)是一个包含至少一个整数的区间。
举个例子来说吧,比如我们输入a=1.2 b=1.3 ,那么:
当k=1时, 区间为(1.2 , 1.3) 其中没有整数;
当k=2时, 区间为(2.4 , 2.6) 其中没有整数;
当k=3时, 区间为(3.6 , 3.9) 其中没有整数;
当k=4时, 区间为(4.8 , 5.2) 其中包含了一个整数5。
所以使得区间(1.2*k, 1.3*k)包含一个整数的最小正整数k是4。

Input

两个非负实数a,b。

Output

最小的k的值。

Sample Input

1.2 1.3

Sample Output

4

Hint

HINT

a,b整数部分不超过2^31-1,a,b小数部分位数不超过300位。

发现[a,b]的答案k等价于[a-1,b-1]的答案k,那么假设\(a \leq b\),那么一定可以让\(a <1 \),这时候如果\(b > 1\) 那么答案就是1.否则我们把条件转换一下:\(a*k \leq x \leq b*k\)等价于\(x/b \leq k \leq x/a\),把问题转换成了一个子问题。这样就可以递归下去做了,最后再一步步乘回来,需要高精度小数乘法。

发表评论

电子邮件地址不会被公开。 必填项已用*标注