题解 CF1152C 【Neko does Maths】

不妨设$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}) $