N个数的最大公约数最小公倍数和最小公倍数和Hankson问题求解

一。基本要求：
求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的个数；
样例输入
41 1 96 288
95 1 37 1776
样例输出
6
2
一.基本要求
1.算法设计
a.先求两给数的最大公约数gy（int a，int，b）
b.给所有数从小到大排序
c.先求出第一个数和下一个数的最大公约数
d.在将求出的最大公约数和下一个数计算，求出他们俩的最大公约数。
e.循环d，直到数据结束
f.求最小公倍数 所有数据相乘在除以最大公约数。

2.算法实现

#define N 100    
 int gys(int a,int b);           
int main()     
{    
int a[N];   
int n;    
int i,j,t;    
int gy,gb;    
printf("请输入数的个数：");   
 scanf("%d",&n);    
 for(i=0;i<n;i++)        
 scanf("%d",&a[i]);      //输入数据    
 for(i=0;i<n-1;i++)              //给数据从小到大排序，    
    {        
           for(j=0;j<n-i;i++)       
         {            
           t=a[j];           
          a[j]=a[j+1];           
          a[j+1]=t;        
         }    
  }    
int k=a[0];          
for(i=0;i<n;i++)              
{   
      int c;                     //将钱两个数的最大公约数 和下一个数求出最大公约数   以此类推      
      c=gys(a[i],a[i+1]);   
      for(i=2;i<n;i++)    
       {        
          gy=gys( c,a[i]);         
       }     
}    
printf("最大公约数是：%d\n",gy);    
for(i=1;i<n;i++)   
   {       
     k=k*a[i];    
   }    
gb=k/gy;                //求出最小公倍数   所以数的乘积/最大公约数     
printf("最大公倍数是：%d\n",gb);     
}     
 int gys(int a,int b)//求最大公约数    
  {       
  int temp,t1;     
   temp=(a>b)?b:a;     
  while(temp>0)    
           {    
                    if(a%temp==0&&b%temp==0) 
                    break;    
                    temp--;     
           }     
                return temp;     
 }

3.1. 调试、测试及运行结果

二.提高要求
1.算法设计
a.最大公约数gy（x，a0）=a1
b.b1是x的最大公倍数，所以b1最大不会超过x的平方
c，x枚举，从1开始；
d.找出满足条件的数，个数就加1；
2.算法实现

#include<stdio.h>
#include<math.h>
    int gy(int a,int b)  //求最大公约数
    {    
    int temp;
     while(a%b)
    {
    temp=a%b;
     a=b;
    b=temp;
     }
      return b;
    }
     int main()
   {
    int a0,a1,b0,b1,c[100];
    int i,j,k,n,x,y,z;
    int sum=0;
        scanf("%d",&n);
    for(i=0;i<n;i++)     //输入数据
    {
        scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
        x=a0/a1;
        y=b1/b0;
        z=(int)sqrt(b1);    //x最大的公倍数 是 x平方
        for(j=1;j<=z;j++)
            if(b1%j==0)   //b1能整除x
            {

                if(j%a1==0&&gy(j,a0)==1&&gy(b1/b0,b1/j)==1) //x能整除a1，并x和a0的最大公约数是1
                    sum++;
                int k=b1/j;
                if(j==k)  // b1=x的平方
                    continue;
                if(k%a1==0&&gy(k/a1,x)==1&&gy(y,b1/k)==1)  
                    sum++;
            }
       
                c[i]=sum;
                sum=0;
    }
    for(i=0;i<n;i++)
    printf("%d\n",c[i]);     
        return 0;
    }

3.1. 调试、测试及运行结果

四．心得体会 除了枚举法，当然用分解质因数的方法更快，但我不太会，还需要继续学习。