已知两个数字的gcd lcm 求两个数字的最小值
作者:
Draper
,
2022-04-08 20:25:26
,
所有人可见
,
阅读 205
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
int t;
long long res;
long long gcd(long long a, long long b)
{
return b == 0? a: gcd(b, a % b);
}
int main()
{
cin >> t;
while(t --)
{
long long l, g, res = INF;
cin >> g >> l;
long long k = l / g;//k = x * y,x y 互质
for(int i = 1; i <= sqrt(k); i ++)
{
if(k % i == 0 && gcd(i, k / i) == 1)
res = min(res, i + k / i);
}
//res 是俩个质数的和 a 是x*g, b是y*g
cout << res * g << endl;
}
return 0;
}