欢迎您来我的网站看这篇题解!
Problem
Neko has two integers a a a and b b b. His goal is to find a non-negative integer k k k such that the least common multiple of a + k a+k a+k and b + k b+k b+k is the smallest possible. If there are multiple optimal integers k k 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 ≥ 0 k\ge 0 k≥0 使 min lcm ( a + k , b + k ) \min\operatorname{lcm}(a+k,b+k) minlcm(a+k,b+k),若有多个 k k k,取最小的。
1 ≤ a , b ≤ 1 0 9 1\le a,b\le10^9 1≤a,b≤109
Solution
这道题还是挺妙的,用到了几个知识点。
- lcm ( a + k , b + k ) = ( a + k ) ( b + k ) gcd ( a + k , b + k ) \operatorname{lcm}(a+k,b+k)=\frac{(a+k)(b+k)}{\gcd(a+k,b+k)} lcm(a+k,b+k)=gcd(a+k,b+k)(a+k)(b+k)
- ( a + k ) ( b + k ) gcd ( a + k , b + k ) = ( a + k ) ( b + k ) gcd ( b + k , a − b ) \frac{(a+k)(b+k)}{\gcd(a+k,b+k)}=\frac{(a+k)(b+k)}{\gcd(b+k,a-b)} gcd(a+k,b+k)(a+k)(b+k)=gcd(b+k,a−b)(a+k)(b+k)
我们将最小公倍数转化为最大公因数,且利用辗转相除法得出了一个定值 a − b a-b a−b。
如果某个 k k k 会使得原式变小,那么肯定会使得 gcd ( b + k , a − b ) > 1 \gcd(b+k,a-b)>1 gcd(b+k,a−b)>1,也就是说 b + k b+k b+k 与 a − b a-b a−b 具有公因数。我们只需要枚举这样的 b + k b+k b+k 就好,缩小了枚举的范围。
具体地,我们枚举 a − b a-b a−b 的因数 x x x;为了使 b + k b+k b+k 是 x x x 的(最小的)倍数:
- 若
b%k==0
则 k = 0 k=0 k=0 - 若
b%k!=0
k = ( b − ⌊ b x ⌋ ⋅ x ) k=(b-\lfloor \frac bx\rfloor\cdot x) k=(b−⌊xb⌋⋅x)
我们使用 O ( a − b ) O(\sqrt{a-b}) O(a−b) 的时间枚举 a − b a-b a−b 的因数,计算满足条件的最小的 k k k,并尝试用此时的 lcm ( a + k , b + k ) \operatorname{lcm}(a+k,b+k) lcm(a+k,b+k) 去更新答案即可。
需要注意特判 a = b a=b a=b 的情况,此时 a − b = 0 a-b=0 a−b=0,不会存在这样的 k k 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;
}