链接: https://codeforces.com/contest/1152/problem/C
题意: 给两个数 a 和 b, 找到一个最小的 k, 使得 a+k 和 b+k 的 lcm 最小
题解: 假设 a>b,gcd(a,b)=gcd(b,a-b), 所以我们要求的 gcd(a+k,b+k) 可以转化成 gcd(b+k,a-b), 令 d=gcd(b+k,a-b), 则 d 是 a-b 的因数, 枚举这个因数, 枚举过程中不断更新最小的 lcm 对应的 k, 若 lcm 相等, 就直接更新最小 k
代码:
- //#include<bits/stdc++.h>
- #include<iostream>
- #include<vector>
- #include<stack>
- #include<string>
- #include<cstdio>
- #include<algorithm>
- #include<queue>
- #include<map>
- #include<set>
- #include<cmath>
- #include<iomanip>
- #define inf 0x3f3f3f3f
- using namespace std;
- typedef long long ll;
- const int M = int(1e7) * 2 + 5;
- ll gcd(ll a, ll b)
- {
- return b ? gcd(b, a % b) : a;
- }
- ll lcm(ll a, ll b)
- {
- return a * b / gcd(a, b);
- }
- ll d, k, tem;
- signed main()
- {
- ll a, b; cin>> a>> b;
- ll c = abs(a - b);
- if (a <b) swap(a, b);
- vector<ll> div;
- for (ll i = 1; i * i <= c; i++) { // 筛出 a-b 的因数
- if (c % i == 0)
- div.push_back(i);
- if (i * i != c)// 判断是否为平方数
- div.push_back(c / i);
- }
- if (a == b){ // 特判 a=b 的情况
- cout << 0 << endl;
- return 0;
- }
- sort(div.begin(), div.end());
- ll ans = inf, tlcm = inf;
- //cout << div.size() << endl;
- d = div[0];
- k = (d - a % d) % d; // 已知 d 求解 k
- tem = lcm(a + k, b + k);
- ans = k;
- tlcm = tem;
- for (int i = 1; i < div.size(); i++) { // 枚举所有的因数
- d = div[i];
- k = (d - a % d) % d;
- tem = lcm(a + k, b + k);
- /*cout << i;
- cout << "tem=" << tem << "" <<"tlcm=" << tlcm << endl;
- cout << "k=" << k << endl;*/
- if (tem < tlcm) { // 以 lcm 最小为依据更新 k
- ans = k;
- tlcm = tem;
- }
- else if (tem == tlcm) {
- ans = min(ans, k);
- }
- //cout << "ans=" << ans << endl;
- }
- cout << ans << endl;
- return 0;
- }
备注: 由于一开始 inf 设置过小, 循环从 0 开始会导致在数据过大时无法更新 lcm
来源: http://www.bubuko.com/infodetail-3046104.html