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

1，题目要求：

基本要求： 求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题。
1.程序风格良好(使用自定义注释模板)
2.提供友好的输入输出，并进行输入数据的正确性验证。
提高要求：

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

2，题目分析

（1） 求N个数的最大公约数和最小公倍数。
求N个数的最大公约数和最小公倍数，和求2个数的思路基本一致，即每两个求一次，用上次求出的最大公约数和最小公倍数和下一个数求。

（2） 求满足条件的x的值。

输入N组，每组均为四个正整数a0，a1，b0，b1，其中x的值满足:

① a1=gcd(x,a0)

② b1=multiple(x,b0);

③ a1<x<b1.
3，算法构造
基本要求：

提高要求：

4，算法实现
（1），基本要求

#include<stdio.h> 
 int gcd (int a,int b)			//求最大公约数的算法
{ 
 if(a%b==0)
        returnb;   
else  
       return gcd(b,a%b);
 }

 int multiple (int a,int b)      	/*自定义函数求两数的最小公倍数*/
{
     intgcd(int a,int b);        	 /*自定义函数返回值类型*/
      int temp;
      temp=gcd(a,b);        		 /*再次调用自定义函数，求出最大公约数*/
     return  (a*b/temp);      		/*返回最小公倍数到主调函数处进行输出*/
}

int main() 
{ 
       int N,a[20],k,i; 
     printf("请输入数字个数："); 
     while(~scanf("%d",&N))                 
       { 
                for(i=0;i<N;i++)				//输入N组数
              		 scanf("%d",&a[i]);  
                k=a[0];
                 for(i=1;i<N;i++) 
                          k=gcd(k,a[i]);
                printf("这%d个数的最大公约数是%d\n",N,k);
                 for(int j=0;j<N;j++)
                    	k=multiple(k,a[j]);
                 printf("这%d个数的最小公倍数是%d\n",N,k);
  }                                     
  return 0; 
}

2，提高要求：

#include<iostream>
using namespace std;
int gcd (int a,int b)                           //求两个数的最大公约数 
{  if(a%b==0)
       return b;   
else  
       return gcd(b,a%b);
}

 int multiple (int a,int b)                  //求两个数的最小公倍数 
{
  int gcd(int a,int b);             
  int temp;
  temp=gcd(a,b);                       
  return (a*b/temp);                
}

int handle(int a0,int a1,int b0,int b1)
{                                   
 int count=0;            //计数器 
 if(!(a0%a1==0&&b1%b0==0))
 {
       printf("输入错误！");
       exit(1); 
 }

 for(int x=a1;x<=b1;x++)            //a1<x<b1
       if((a1==gcd(x,a0))&&(b1==multiple(x,b0)))
             {
                  count++;
             }

 if(count==0)				//是我想多了，这里直接return count；就好，不用这么麻烦
       return 0;
 else
       return count;
}

struct arr
{
       int a0;
       int a1;
       int b0;
       int b1;
};

int main()
{
 int N;
 struct arr arry[40];
 scanf("%d",&N);
 for(int i=0;i<N;i++)
       scanf("%d%d%d%d",&arry[i].a0,&arry[i].a1,&arry[i].b0,&arry[i].b1);
 for(int j=0;j<N;j++)  
       printf("%d\n",handle(arry[j].a0,arry[j].a1,arry[j].b0,arry[j].b1));
 return 0;
}

5， 调试、测试及运行结果
（1），调试
基本要求：

提高要求：

（2），测试及运行结果

基本要求：

提高要求：

6，经验归纳： 学到了输入多组数据的方法：while (~scanf("%d",&m)) ，其功能是循环从输入流读取m，直到遇到EOF为止，等同于while(scanf("%d%d",&m,&n)!=EOF)。scanf()函数返回成功赋值的数据项数，出错时则返回，EOF定义为-1。~是按位取反，-1十六进制补码表示为0x ffffffff，f是二进制的1111，取反后就全部变成0了，于是while结束。只有返回值为EOF（即-1）时，其取反的的值（即while循环的判断条件）才为0，才能结束循环，其它输入情况下（无论是否输入成功）while循环的判断条件为非0，即为真。这种写法的漏洞在于：一但输入的值为字母、符号之类的，scanf赋值不成功把读到的内容又返回到stdin的缓冲区（假设这个值为t），其取反得到的值使while又进入到下一次循环，scanf又从stdin缓冲区里读到了原先吐回的t，如此成了死循环。 其次，这次上机使用C语言，感觉对自顶向下，逐步求精的概念有了更深的理解。同时，对题目的抽象能力有了一定的建立。