已知gcd和lcm求a+b最小和？------数论

题意
给出2个数a，b的 gcd(最大公约数n) 和 lcm(最小公倍数m)，求所有符合条件的a，b中， 的最小
值。
思路
暴力枚举。根据 gcd(a,b)lcm(a,b)=ab 我们可以得到 ab的值，不妨假设a<b ，那么我们可以在$$[1,\sqrt{a\ast b}]$$
区间 内枚举a 的取值，再根据ab 计算出b的值，验证是否满足gcd和lcm约束，即可找
到所有可能的(a,b) 取值。然后考虑题目要求是找出a+b 的最小值，既然a*b 的值是固定的，那么a
和b 的差值越小a+b 的值也就越小，因此我们可以逆序枚举 a的值，找到的第一个满足条件的(a,b) 时即为正确答案。最后考虑进行一点点优化，由于gcd(a,b)=n 那么a 一定是 n的整数倍，因此我们只需要
枚举区间内 n的整数倍的值即可。

代码：

#include<bits/stdc++.h> using namespace std; #define ll long long ll Gcd(ll a,ll b){return b==0?a:Gcd(b,a%b);} int main() { ll gcd,lcm,a,b,x; int t; cin>>t; while(t--) { cin>>gcd>>lcm; x=gcd*lcm; a=sqrt(x); a=a-a%gcd; //快速找出从 a~1 中为 gcd 的倍数的数 while(1) { if(x%a==0) { b=x/a; //满足 a*b = lcm; if(Gcd(a,b)==gcd) break; //那么只要这两个数满足 (a,b)=gcd 就找到了 } a-=gcd; //否则减去 gcd } cout<<a+b<<endl; } return 0; }

那么我们可不可以继续优化呢？答案是可以！
思路：
已知最大公因数为g，最小公倍数为l，那么两个数可设为x * g和y * g，又因为两个数的乘积==g*l，即x * y == l/g，求最小和即求最小的x+y，问题转换为了：在x和y互质的情况下已知x * y,求x+y的最小值为多少，此时枚举1-sqrt(x * y)的值即可。
note:
注意不要忘记x和y一定要互质，这样才能保证g仍然是最大公因数。

意思是：
LCM比GCD多的因子进行适当分配就可以使B-A最小
所以就应该把LCM÷GCD的值分解质因数（LCM/GCD可求得LCM比GCD多的因子）

代码：

while (cin >> t){while (t--){ll l, g, k, res = INF;cin >> g >> l;k = l / g;//k = x+y//只需要枚举L/G的约数，枚举的一个x在a中，那么另一个(L/G)/x就是在b中，for (int x = 1; x <= sqrt(k); x++) //这一步是将k分解质因子if (k % x == 0 && gcd(x, k / x) == 1)// 因为要保证 x *y=k的前提下，两个数互素res = min(res, x + k / x); //取最小的cout << res * g << endl; //因为后面 a+b =g(x,k/x) .因为g是a，b的最大公因数} //所以肯定含有g，又因为最大公倍数有比g多的因子，且不相同（相同的被g拿去了）}

总结

以上是生活随笔为你收集整理的已知gcd和lcm求a+b最小和？------数论的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。