CF1152C Neko does Maths

欢迎您来我的网站看这篇题解！

Problem

Neko has two integers $a$ and $b$. His goal is to find a non-negative integer $k$ such that the least common multiple of $a+k$ and $b+k$ is the smallest possible. If there are multiple optimal integers $k$, he needs to choose the smallest one.

Given his mathematical talent, Neko had no trouble getting Wrong Answer on this problem. Can you help him solve it?

找 $k\ge 0$ 使 $\min \mathrm{lcm}(a+k,b+k)$，若有多个 $k$，取最小的。

$1\le a,b\le 10^9$

Solution

这道题还是挺妙的，用到了几个知识点。

1. $\mathrm{lcm}(a+k,b+k)=\frac{(a+k)(b+k)}{\gcd (a+k,b+k)}$
2. $\frac{(a+k)(b+k)}{\gcd (a+k,b+k)}=\frac{(a+k)(b+k)}{\gcd (b+k,a-b)}$

我们将最小公倍数转化为最大公因数，且利用辗转相除法得出了一个定值 $a-b$。

如果某个 $k$ 会使得原式变小，那么肯定会使得 $\gcd (b+k,a-b)>1$，也就是说 $b+k$ 与 $a-b$ 具有公因数。我们只需要枚举这样的 $b+k$ 就好，缩小了枚举的范围。

具体地，我们枚举 $a-b$ 的因数 $x$；为了使 $b+k$ 是 $x$ 的（最小的）倍数：

• 若 b%k==0 则 $k=0$
• 若 b%k!=0 $k=(b-\lfloor \frac{b}{x}\rfloor \cdot x)$

我们使用 $O(\sqrt{a-b})$ 的时间枚举 $a-b$ 的因数，计算满足条件的最小的 $k$，并尝试用此时的 $\mathrm{lcm}(a+k,b+k)$​ 去更新答案即可。

需要注意特判 $a=b$ 的情况，此时 $a-b=0$，不会存在这样的 $k$。

Code

LL gcd(LL a,LL b)
{
	if(!a) return b;
	if(!b) return a;
	return gcd(b,a%b);
}

LL lcm(LL a,LL b)
{
	return a*b/gcd(a,b);
}

LL k,minlcm;
LL a,b;
void test(LL x)
{
	LL aa=b/x;
	LL bb=b%x;
	if(bb) aa++;
	aa*=x;
	LL kk=aa-b;
	if(lcm(a+kk,b+kk)<minlcm||(lcm(a+kk,b+kk)==minlcm&&kk<k))
	{
		k=kk;
		minlcm=lcm(a+kk,b+kk);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cout.precision(10);
	int t=1;
//	cin>>t;
	while(t--)
	{
		k=100000000000ll;
		cin>>a>>b;
		if(a==b)
		{
			cout<<0<<endl;
			return 0;
		}
		if(a<b) swap(a,b);
		minlcm=lcm(a,b);
//		cout<<minlcm<<endl;
		for(LL i=1;i*i<=a-b;i++)
		{
			if((a-b)%i==0)
			{
				test(i);
				test((a-b)/i);
			}
		}
		cout<<k<<endl;
	}
	return 0;
}