题解 CF1152C 【Neko does Maths】

ljc20020730 · 2019-04-26 18:54:32 · 题解

不妨设a>b

显然lcm(a+k,b+k)=\frac{(a+k)(b+k)}{gcd(a+k,b+k)}

由辗转相减法可知gcd(a,b)=gcd(b,a-b)，

所以原式可化为lcm(a+k,b+k)=\frac{(a+k)(b+k)}{gcd(b+k,a-b)}

对于a-b的值是定值，那么我们就可以枚举a-b的因子w然后反过来O(1)求出最小的k就行了。

若b \% w = 0 那么 k = 0 否则 k = (\left \lfloor \frac{b}{w} \right \rfloor + 1)w-b

复杂度 O(\sqrt{a-b})