总时间限制: 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 }