一、题目名称：求N个数的最大公约数和最小公倍数
二、题目内容：Hanks博士是BT ( Bio-Tech，生物技术)领域的知名专家，他的儿子名叫Hankson。现在，刚刚放学回家的Hankson正在思考- -个有趣的问题。今天在课堂上，老师讲解了如何求两个正整数c1和c2的最大公约数和最小公倍数。现在Hankson认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的:已知正整数a0,a1,b0,b1，设某未知正整数x满足:
1、x和a0的最大公约数是a1;
2、x和b0的最小公倍数是b1。
Hankson的“逆问题"就是求出满足条件的正整数x。但稍加思索之后，他发现这样的x并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x的个数。请你帮助他编程求解这个问题。
输入格式
输入第一行为一个正整数n,表示有n组输入数据。接下来的n行每行一组输入数据，为四个正整数a0，a1， b0，b1，每两个整数之间用一个空格隔开。输入数据保证a0能被a1整除，b1能被b0整除。
输出格式
输出共n行。每组输入数据的输出结果占一行，为一个整数。对于每组数据:若不存在这样的x，请输出0;若存在这样的x，请输出满足条件的x的个数;
样例输入
2
41 1 96 288
95 1 37 1776
样例输出
6
2
数据范围与约定
对于50%的数据，保证有1sa0，a1, b0, b1≤10000且ns100
对于100%的数据，保证有1≤a0，a1, b0, b1s2,000,000,000 且n≤2000。
样例解释
第一组输入数据，xx 可以是9,18,36,72,144,2889,18,36,72,144,288,共有66个。
第二组输入数据，xx 可以是48,177648,1776，共有22个。
二、算法设计：
1.n个数的最大公约数的求解，首先要输入n个数，并将数字进行保存。求解时求两个的最大公约数gcd(x1,x2),再将所得的数与第三个求解最大公约数gcd( gcd(x1,x2) , x3 ),如此递归调用即可求出n个数的最大公约数。
2.n个数的最小公倍数的求解，首先求两个的最小公倍数(x1，x2)/gcd(x1,x2),再将所得的最小公倍数与第三个求最小公倍数，如此递归调用即可求出n个数的最小公倍数。
图1：流程图
四、调试截图：
调试每一次递归循环中公约数和最小公倍数的值.
图2：第一次
图3：第二次
图4：第三次
五、测试结果：
- 测试两个数的最大公约数和最小公倍数
测试代码：
#include <stdio.h>
int gys(int x, int y)//辗转相除法
{
int a;
if (x<y) { //将大的数排在前面
a = x;
x = y;
y = a;
}
while (x%y != 0) { //一直循环直到y是x的因数
a = x%y;
x = y; // 不断取除数 作为x
y = a; //不断取余数 作为y }
return y; //当y是x的因数时，y就是最大公因数
}
int gbs(int x, int y)
{
int result = (x*y) / (gys(x, y));
return result;}
void main()
{
int a=gys(3,9);
int b=gbs(4,12);
printf("最大公约数为%d\n",a);
printf("最小公倍数为%d\n",b);
}
|
测试用例 |
int a=gys(3,9) |
int b=gbs(4,12) |
|
预测结果 |
3 |
12 |
|
结果 |
3 |
12 |
图5:测试1
- 用例测试：
|
测试用例 |
1 2 3 4 |
2 3 4 5 |
|
预测结果 |
gyemax=1 gbsmin=12 |
gysmax=1 gbsmin=60 |
|
结果 |
gyemax=1 gbsmin=12 |
gyemax=1 gbsmin=60 |
图6：测试2
六、总结：
1.在运行时一直弹出scanf()有错误，vs2015中要用scanf_s(),调整后可以运行。
2.在求最小公倍数时不知道怎么求，在网上搜了之后才明白，直接用两个数的乘积除以他们的最小公倍数就行了。
3.两个数的最小公倍数和最大公约数知道怎么求，但一直想不明白n个数的怎么求，最后在在将所得的数与第三个求解最大公约数gcd( gcd(x1,x2) , x3 ),如此递归调用即可求出n个数的最大公约数。最小公倍数同理，对递归的运用还是不太熟练。
4.在做提高题时一直么有思路，在网上搜的中间有很多算法看不太懂，就没做，还得继续努力，学习算法。