Codeforces Round #554 (Div. 2) C. Neko does Maths

题意：

求lcm(a+k,b+k)的k，使lcm最小，给出a，b

思路：lcm最小，则gcd(a+k,b+k)最大，gcd(a+k,b+k)==gcd(a+k,b-a)，b-a是固定的，从这里入手，找出a-b的所有因数，一个一个试，找出最小的lcm

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, ans = 1e18 + 5, k;
vector<ll> v;
ll lcm(ll x, ll y) {
return x * y / __gcd(x, y);
}
int main() {
cin >> a >> b;
if(a > b)
swap(a, b);
for(int i = 1; i * i <= (b - a); i++) {
if((b - a) % i == 0) {
v.push_back(i);
if(i * i != (b - a))
v.push_back((b - a) / i);
}
}
for(int i = 0; i < v.size(); i++) {
ll t = 0;
if(a % v[i] != 0)
t = v[i] - a % v[i];
ll tmp = lcm(a + t, b + t);
if(ans > tmp) {
k = t;
ans = tmp;
}
if(ans == tmp)
k = min(k, t);
}
cout << k;
return 0;
}

最后

以上就是朴素板凳为你收集整理的Codeforces Round #554 (Div. 2) C. Neko does Maths的全部内容，希望文章能够帮你解决Codeforces Round #554 (Div. 2) C. Neko does Maths所遇到的程序开发问题。

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