首页 > 代码库 > Uva 11889 Benefit (lcm与gcd)
Uva 11889 Benefit (lcm与gcd)
题意:给你两个数,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; }
Uva 11889 Benefit (lcm与gcd)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。