题目描述

（描述为翻译，翻译来自洛谷） 给定两个正整数a,b，找到非负整数k使a+k与b+k的最小公倍数最小，如有多解输出最小的k

$a,b\le 10^6$ 对于这种题我们显然需要一些数论知识来帮助我们找到思路 那么我们首先想到的是lcm和gcd是有关系的 即$lcm(a,b)=\frac{a\ast b}{gcd(a,b)}$ 那么在这道题中就是$lcm(a+k,b+k)=\frac{(a+k)\ast (b+k)}{gcd((a+k),(b+k))}$ 然后我们可以想到gcd的一些性质 那么由更相减损术我们可以知道$gcd(a,b)=gcd(b,a-b)$其中，a >b; 那么我们就可以把原式子中的$gcd(a+k,b+k)$写成$gcd(b+k,a-b)$ 那么我们考虑，设 $x=gcd(b+k,a-b)$那么x一定是a-b的因子的其中一个，这时候我们只需要算出一个k使x是b+k和a-b的gcd我们就可以求出一个lcm， 这里当$b\mathrm{m}\mathrm{o}\mathrm{d}x==0$时k = 0; !=时 k = b/x * x + x; 这里的除是向下取整，这样就保证了x是b+k的最大因子。 因此我们可以枚举a-b的所有因子，求出对应的k和lcm，对于每个结果进行比较求min即可。

没想到的是，k是会爆ll的 所以记得开ll写

$$Code$$

#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define ll long long using namespace std; inline ll gcd(ll a, ll b){//没用 return a % b == 0 ? b : gcd(b, a % b); } ll a, b, k, t; ll ans = 1e18; int main() { cin >> a >> b; if(a < b){ a ^= b, b ^= a, a ^= b; } ll num = 1e18; for(ll i = 1; i * i <= a-b; ++i){//i,j都为枚举的因子 ll tk; if((a-b) % i == 0){ ll j = (a-b) / i; if(b % i == 0) tk = 0; else tk = (b / i + 1) * i - b; ll num = (a + tk) * (b + tk) / i; if(num < ans) ans = num, k = tk; if(num == ans) k = min(k, tk); if(b % j == 0) tk = 0; else tk = (b/j + 1) * j - b; num = (a + tk) * (b + tk) / j; if(num < ans) ans = num, k = tk; else if(num == ans) k = min(k, tk); } } cout << k << endl; }