题意:给你两个数,a,c,求出 lcm(a,b)==c 时的 b 的最小值
思路:我们知道一个性质 gcd(a,b)*lcm(a,b) = a*b
由此我们可以得到 b = gcd(a,b)*lcm(a,b)/a
那我们可以先用 lcm(a,b)/a 计算出假定的b值
如果 gcd(a.b)==1 那么b的最小值确定
如果 gcd(a,b)!=1 我们就要通过计算来找到
计算方法为 a=a/gcd(a,b) b=b*gcd(a.b)
样例:
4
6 12
2 6
32 1760
7 16
结果: 4 3 55 NO SOLUTION
#include <iostream>
#define ll long long
using namespace std; int gcd(int a,int b)
{
if(b==) return a;
else return gcd(b,a%b);
} int main()
{
int t;
cin>>t;
while(t--)
{
int a,c;
cin>>a>>c;
if(c%a!=)
{
cout<<"NO SOLUTION"<<endl;
continue;
}
int ans=c/a;
int k=gcd(a,ans);
while(k!=)
{
a=a/k;
ans=ans*k;
k=gcd(a,ans); }
cout<<ans<<endl;
}
return ;
}