题意

设 $gcd(a, b) = n, lcm(a, b) = m $ ，T组数据，每次输入n, m，求所有符合条件的a, b中，$a+b$ 的最小值。

其中$t \le 100, n \le 10000, m\le 1e9$ 。

输入

2
3 30
5 100

输出

21
45

解释：

​ $15$ 和 $6$ 的最大公约数是 $3$ ，最小公倍数是 $30$ 。

​ $20$ 和 $25$ 的最大公约数是 $5$ ，最小公倍数是 $100$ 。

题解

$$ lcm(a, b) =\frac{a * b}{gcd(a, b)} \\\\ \frac{lcm(a ,b)}{gcd(a, b)} = \frac{a}{gcd(a, b)} * \frac{b}{gcd(a, b)} $$

记
$$ c = \frac{lcm(a ,b)}{gcd(a, b)} \\\\ \frac{a}{gcd(a, b)} = a’ \\\\ \frac{b}{gcd(a, b)} = b’ $$
则：$gcd(a’, b’) = 1$

去枚举所有的 $a’$ 和 $b’ = \frac{c}{a’}$。则$a + b = (a’ + b’)*gcd(a, b)$

每次枚举的复杂度是$\sqrt c$

代码

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
LL n, m;

LL gcd(LL a, LL b){
    return b ? gcd(b, a % b) : a ;
}
int main(){
    int T;
    cin >> T;
    while(T --){
        cin >> n >> m;

        LL c = m / n;
        LL ans = 1e10;

        for(LL i = 1; i <= c / i; ++ i){
            if(c % i == 0){
                if(gcd(i, c / i) == 1){
                    ans = min(ans , (i + c / i) * n);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}