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. 調試、測試及運行結果
四．心得體會 除了枚舉法，當然用分解質因數的方法更快，但我不太會，還需要繼續學習。