本文共 3134 字，大约阅读时间需要 10 分钟。

N个数的最大公约数和最小公倍数。

题目内容及要求：

1.求N个数的最大公约数和最小公倍数。

2.提高要求： 题目描述 已知正整数a0,a1,b0,b1。设某未知正整数x 满足： 1． x 和a0 的最大公约数是a1； 2． x 和 b0 的最小公倍数是 b1。 求解满足条件的 x 的个数 输入 第一行为一个正整数n，表示有n 组输入数据。接下来的n 行每行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证a0 能被a1 整除，b1 能被b0 整除。 [说明]: 第一组输入数据，x 可以是9、18、36、72、144、288，共有6 个。 第二组输入数据，x 可以是 48、1776，共有 2 个。 [数据规模]： 对于 50%的数据，保证有1≤a0，a1，b0，b1≤10000 且n≤100。 对于 100%的数据，保证有 1≤a0，a1，b0，b1≤2,000,000,000 且 n≤2000。 输出 若不存在这样的x，请输出0； 若存在这样的x,请输出满足条件的x的个数。 样例输出 2 41 1 96 288 95 1 37 1776

算法设计

1.对于求N个数的最大公因数和最小公倍数。

1）对于最大公因数，用辗转相除法求最大公约数。可以使用递归和迭代两种写法。 2）对于最小公倍数，两个数的乘积等于这两个数的最大公因数和最小公倍数的乘积。 2.对于提高要求中的Hanson“逆问题”的解决。首先由最大公因数和最小公倍数的性质可知，令p = a0/a1，q = b1/b0，它们与x的公因数为1，并且x也是b1（最小公倍数）的一个因子。所以令x从1到sqrt(b1)中是b1（最小公倍数）的一个因子，除此之外还有b1/x，也可能是其中的一个因子，用以上条件进行判定。

求两个数的最大公约数：

int GCD(int m,int n){   	//递归写法 	if(n == 0)	{   		return m;	}	return GCD(n,m%n);	/*	//迭代写法            while(n != 0){            int t = n;            n= m % n;            m = t;        }        return m;    }	*/}

求两个数的最小公倍数:

int LCM(int m,int n){   	return (m*n)/GCD(m,n);}

判断输入数据的正确性

int inspect(int *array,int number){   	for(int i = 0;i

Hankson的相关算法

int Hanson(int line_number){   	int number = 0;	int count[line_number];	while(line_number--) 	{           int a0,a1,b0,b1;                //对输入数据进行判断         while(1)        {           	cin>>a0>>a1>>b0>>b1;        	if(a0%a1 != 0 || b1%b0 != 0)        	{           		cout<<"输入数据有误，请重新输入这组数据!"<

相关运行结果截图

全部代码

//辗转相除法， 又名欧几里得算法（Euclidean algorithm），目的是求出两个正整数的最大公约数 /***实现功能：1.N个数的最大公约数和最小公倍数 *2.已知正整数a0,a1,b0,b1,设某未知正整数x满足：*(1)x和a0的最大公约数为a1;*(2)x和b0的最小公倍数为b1;*输入数据 保证a0能被a1整除,b1能被b0整除。*对于每组数据：若不存在这样的x,请输出0;若存在这样的x,请输出满足条件的x的个数; *对于两个整数，它们两个的乘积等于它们的最大公约数和最小公倍数的乘积。* 使用辗转相除法求最大公约数 */ #include "iostream"using namespace std;//N个数的最大公约数 int GCD(int m,int n){   	//递归写法 	if(n == 0)	{   		return m;	}	return GCD(n,m%n);	/*	//迭代写法            while(n != 0){            int t = n;            n= m % n;            m = t;        }        return m;    }	*/}//N个数字的最小公倍数 int LCM(int m,int n){   	return (m*n)/GCD(m,n);}//判断输入数据的正确性 int inspect(int *array,int number){   	for(int i = 0;i
   
    >a0>>a1>>b0>>b1;        	if(a0%a1 != 0 || b1%b0 != 0)        	{           		cout<<"输入数据有误，请重新输入这组数据!"<
    
     >choose_number;		if(cin.fail() || choose_number != 1 && choose_number != 2)            //cin.fail()  判断cin状态               		{   			system("cls");			cout<<"输入有误，请重新输入你的选择!"<
     
      >number;			int array[number];			cout<<"请输入"<
      
       <<"个数字(两个数字之间用空格隔开)："<
       
        >array[i];				}								//判断输入数据是否准确 				flag = inspect(array,number);				}			int lcm = array[0];	//存放最小公倍数			int gcd = array[0]; //存放最大公约数 			for(int i = 0;i
        
         >line_number; Hanson(line_number); } return 0;}
        
       
      
     
    
   

总结

1.定义了整形数line_number，如果输入字母或者其他非法字符，就会出现乱码现象，并且无法操作，只能终止。

解决方法：使用cin.fail()判断cin的状态，如果出现乱码现象，可以使用cin.clear()恢复cin的状态，并使用cin.sync(); //清除缓冲区的数据流 。这样就可以提示输入错误，重新输入。 2.对于动态数组长度问题，这里采用的还是输入数组长度，然后定义数组长度。但在VC环境中会报错。E0028。后面作业中可以使用Vector。vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。 对于解决Hanson“逆问题”的问题上，之前写的代码所占内存过于大。而且对于换行存数据并计算X的个数存在一点问题。如果只测一行数据，可以测。但如果测第二组数据就会显示的结果是正确的结果减一。第三个结果就溢出了。所以借鉴了CSDN上的文章 链接: .

转载地址：http://yuve.baihongyu.com/