分享一下我的思考，不一定对，请指正。如果我们已经知道了两个数a，b(a>0,b>0)的最大公约数为c，最小公倍数d，那么$a*b=c*d$。那么可以暴力枚举a，可以通过$a*b=c*d$算出b，在验算gcd(a, b)=c，维护一个最大值就行，但是复杂度较高。

那我们可以想，a和b的所有质因数与$c*d$的质因子一样，所以我们对$c*d$分解质因数，又因为c中的质因子在a，b中一定都出现过，所以我们对$c*d$分解质因数后的结果减去两倍的c的质因数，那么得出的这个结果中所有的质因子要么在a中出现，在b中没出现；要么在a中没出现，在b中出现。所以我们可以用贪心，现在a，b的基础都是c，我们要将刚才得到的数组中的数都累乘到a或者b上，所以我们可以将所有的数都乘到a或者b上，这样可以使a+b的结果最大。这样复杂度就降为了log(n).

// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>

#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 2e5+10, M = N * 2, INF = 0x3f3f3f3f;

int n, m;
int c, d;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>c>>d; // c 是最大公约数，d是最小公倍数
    LL tmp = c * d;
    unordered_map<int,int> ha;
    for(int i=2;i<=tmp/i;i++){
        if(tmp%i==0){
            int s = 0;
            while(tmp%i==0) s++,tmp/=i;
            ha[i] = s;
        }
    }
    if(tmp>1) ha[tmp] ++;

    tmp = c;
    for(int i=2;i<=tmp/i;i++){
        if(c%i==0){
            int s = 0;
            while(tmp%i==0) s++,tmp/=i;
            ha[i] -= 2 * s;
        }
    }
    if(tmp>1) ha[tmp] -= 2;

    LL a = c, b = c;
    for(auto [x, y]:ha)
        if(y>0){
            for(int i=0;i<y;i++) b *= x;
        }

    cout<<a+b<<endl;
    return 0;
}

---

---

---

---

---

---

有gcd和lcm可以知道ab的乘积，然后根据ab的乘积可以知道这个乘积中包含了两个gcd，用这个乘积除以两次gcd，应该可以得到一组互质的数，这组数分别*gcd就是a跟b。
但是我在考虑a和b是不是总是唯一的呢？根据我的思路的话，我们总是能根据乘积得到一个数，将这个数分解为两个互质的数，从而得到a和b…但是题目又限制了gcd的数值，所以a和b总是唯一的？？

---

---

---