求多个数的最大公约数，最小公倍数以及hanks son问题

基本要求： 求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题。

提高要求：Hanks博士问题 

     基本要求：：首先要明确如何求最大公约数和最小公倍数。有四种算法：辗转相除、stein算法、穷举法、更相减损法。本程序中运用辗转相除法来求两个数的最大公约数；最小公倍数和最大公约数存在关系：两个数的最大公约数和最小公倍数的乘积等于这两个数的乘积。（求最大公约数算法传送门：https://blog.csdn.net/qq_41233643/article/details/88369518）

最大公约数：

/*求多个数的最大公约数*/ 
int GCD()
{
  int k,n;
  long a,b,c,r,m[100];
  //printf("请输入整数个数n: "); 
  scanf("%d",&n);
  for(k=0;k<=n-1;k++)
    { //printf("%d ",k+1);
     scanf("%ld",&m[k]);
    }
  b=m[0];
  for(k=1;k<=n-1;k++)        
  { a=m[k];
    if(a<b)
      { 
      c=a;a=b;b=c;
      }            //  交换a,b，确保a>b
     // gcd(a,b);
    r=a%b;
    while(r!=0)
      { 
          a=b;
          b=r;            //  辗转相除
       r=a%b;
      }
  }
  //printf("(%ld",m[0]);     
  //for(k=1;k<=n-1;k++)
   // printf(",%ld",m[k]);
  printf("%ld\n",b);
}

最小公倍数：

int LCM()
{
    int t,n;
   // printf("请输入n个数：\n") ;
    while(scanf("%d",&t)!=EOF)
    { int l =1;
        while(t--)
        {
            scanf("%d",&n);
             l=lcm(l,n);//此函数为求两个数的最小公倍数函数
        }
        printf("%d\n",l);
    }
}

hanks问题：

思路分析：

由题目： 可以得出

 x和a0的最大公约数是a1；

//x%a1==0&&a0%a1==0     

//gcd(x,a0)=a1

  x和b0的最小公倍数是b1。

//b1%b0==0&&b1%x==0      

//x*b0=b1*gcd(x,b0)

x为b1的约数，于是要从1~根号b1列举，找存在的x，x符合要求就令计数器+1；

代码：

int n;
    int a0,a1,b0,b1;
    scanf("%d",&n);
    while(n--)                //控制测试组数 
    {
        scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
        int temp=0;
        for(int x=1;x<=sqrt(b1);x++ )
        {
            if(b1%x==0)
            {
                if(x%a1==0 && gcd(x/a1,a0/a1)==1 && gcd(b1/x,b1/b0)==1) 
                temp++;
                int y=b1/x;if(y==x) 
                continue;
                if(y%a1==0 && gcd(y/a1,a0/a1)==1 && gcd(b1/y,b1/b0)==1) 
                temp++;
            }
        }

如需源码请：源码下载