题意：给你两个数，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==0) 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!=0) { cout<<"NO SOLUTION"<<endl; continue; } int ans=c/a; int k=gcd(a,ans); while(k!=1) { a=a/k; ans=ans*k; k=gcd(a,ans); } cout<<ans<<endl; } return 0; }
原文：http://www.cnblogs.com/nefu929831238/p/6130346.html