7828:最大公约数与最小公倍数
7828:最大公约数与最小公倍数
总时间限制: 1000ms 内存限制: 65536kB描述
两个正整数的最大公约数是G，最小公倍数是L，它们的和最小是多少？
输入两个不大于10000的正整数G和L，中间用单个空格隔开。数据保证L是G的倍数。输出一个正整数，即最小的和。样例输入
14 280样例输出
126来源《奥数典型题举一反三（小学五年级）》 (ISBN 978-7-5445-2882-5) 模拟试卷一 第6题
1 #include<bits/stdc++.h>
2 using namespace std;
3 int minx,a,b,x,y;
4 int gcd(int x,int y) {
5 if(y==0)return x;
6 return gcd(y,x%y);
7 }
8 int lcm(int x,int y) {
9 return x*y/gcd(x,y);
10 }
11 int main() {
12 cin>>x>>y;
13 minx=1000000;
14 for(int a=x; a<=y; a=a+x)
15 {
16 if(x*y%a!=0)continue;
17 b=x*y/a;
18 if(gcd(a,b)==x&&lcm(a,b)==y)
19 if(a+b<minx)minx=a+b;
20 }
21 cout<<minx;
22 return 0;
23 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-03-15 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录