C. Neko does Maths （gcd）

题目链接：哆啦A梦传送门

题意：已知 a，b，找一个最小的k，使得（a+k) 与 (b+k)的最小公倍数尽可能的小。

题解：假设a>b，那么gcd(a,b)=gcd(a-b,b)。

证：设c=a-b，则gcd(a,b)=gcd(b+c,b)=gcd(b,c)=gcd(a-b,b)。

即 gcd(a+k,b+k)=gcd(a-b,b+k)=c，最后我们就直接枚举(a-b)的因子，也就是最大公约数c就好了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a,b,k,mi;
void solve(LL g)
{
LL item=b/g;
if(b%g) item++;
LL k1=item*g-b;
LL ans=(a+k1)*(b+k1)/g;
if(ans<mi){
mi=ans;
k=k1;
}
}
int main() {
scanf("%lld%lld",&a,&b);
if(a==b) {
printf("0n");
return 0;
}
if(a<b) swap(a,b);
LL item=a-b;
mi=a*b/__gcd(a,b);
for(int i=1;i*i<=item;i++)
{
if(item%i==0){
solve(i);solve(item/i);
}
}
printf("%lldn",k);
}
/*
9 -2
-3 8 -2 1 -6 8 -2 1 -6
*/

最后

以上就是自由保温杯为你收集整理的C. Neko does Maths （gcd）的全部内容，希望文章能够帮你解决C. Neko does Maths （gcd）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。