本文主要是介绍POJ NOI MATH-7828 最大公约数与最小公倍数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
- 问题链接： POJ NOI MATH-7828 最大公约数与最小公倍数 。
- 总时间限制:
- 1000ms 内存限制:
- 65536kB
- 描述
-
两个正整数的最大公约数是G，最小公倍数是L，它们的和最小是多少？
输入 - 两个不大于10000的正整数G和L，中间用单个空格隔开。数据保证L是G的倍数。 输出
- 一个正整数，即最小的和。 样例输入
-
14 280 样例输出 -
126 来源 - 《奥数典型题举一反三（小学五年级）》 (ISBN 978-7-5445-2882-5) 模拟试卷一 第6题
问题分析
不知道如何下手就枚举，靠暴力解决问题。问题是如何枚举？
假设两个正整数是a和b，那么a>0且b>0。G是a和b的最大公约数，假设a=kaG和b=kbG, a+b=(ka+kb)G，明显ka>0且kb>0，得ka+kb>=2。
那么，枚举就按照ka+kb>=2，枚举ka+kb，从2开始。并且满足a+b=(ka+kb)G。
程序说明
程序中，变量i即ka+kb，变量aplusb即a+b，变量j即a，aplusb-j即b。
AC的C++语言程序：
#include <iostream>using namespace std;// 非递归计算最大公约数
int gcd(int m, int n)
{for(;;) {if(n == 0)return m;int temp = m % n;m = n;n = temp;}
}int main()
{int g, l, ans, aplusb;cin >> g >> l;for(int i=2; ;i++) {ans = 0;aplusb = i * g;for(int j=g; j<aplusb; j+=g)if(j / g * (aplusb - j) == l) {if(gcd(j, aplusb - j) == g) {ans = aplusb;break;}}if(ans > 0) {cout << ans << endl;break;}}return 0;
}
这篇关于POJ NOI MATH-7828 最大公约数与最小公倍数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
