題意
給出2個數a，b的 gcd(最大公約數n) 和 lcm(最小公倍數m)，求所有符合條件的a，b中， 的最小
值。
思路
暴力枚舉。根據 gcd(a,b)lcm(a,b)=ab 我們可以得到 ab的值，不妨假設a<b ，那么我們可以在$$[1,\sqrt{a?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最小和？------数论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。