求n个数最大公约数和最小公倍数及Hankson问题
1.求N个数的最大公约数和最小公倍数。
2.Hankson问题。已知正整数a0,a1,b0,b1，设某未知正整数x满足：x和a0的最大公约数是a1； x和b0的最小公倍数是b1。
输入第一行为一个正整数n，表示有n组输入数据。接下来的n行每行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证a0能被a1整除，b1能被b0整除。对于每组数据：若不存在这样的x，请输出0；若存在这样的x，请输出满足条件的x的个数。
算法设计
辗转相除法求最大公约数，利用函数嵌套调用求最小公倍数。
int gongyueshu(int a,int b)/*辗转相除法求两个数的最大公约数*/
{
int temp;
if(a<b)
{temp=a;a=b;b=temp;}
while(b!=0)
{temp=a%b;a=b;b=temp;}
return(a);
}
int gongbeishu(int a,int b)/*求两个数的最小公倍数*/
{
int gongyueshu(int a,int b);
int temp;
temp=gongyueshu(a,b);
return(a*b/temp);
}
定义gys()和gbs()函数，先求出两个数的最小公倍数，再和数组中下一个数求值直到数组中的数循环结束，最终在主函数中调用函数，从而得出n个数的最小公倍数和最大公约数。
Hankson问题
枚举法的基本思想是根据题目的部分条件确定答案的大致范围，并在范围内对所有可能的情况逐一验证，直到全部情况验证完毕。若某个情况验证符合题目的全部条件，则为本问题的一个解；若不符合则本题无解。
调用辗转相除法求最大公约数和函数嵌套调用求最小公倍数。输入正整数n,利用while(n--)语句，依次输入n组数据的a1,a0,b0,b1。求符合条件x时，x=b1/b0*gongyueshu(x,b0)且满足(gongyueshu(x,a0)==a1&&gongbeishu(x,b0)==b1时，符合条件，count++，直到输出结束。
源代码
#include <iostream>
#include <stdlib.h>
#define N 100
using namespace std;
int gongyueshu(int a,int b)/*辗转相除法求两个数的最大公约数*/
{
int temp;
if(a<b)
{
temp=a;
a=b;
b=temp;
}
while(b!=0)
{
temp=a%b;
a=b;
b=temp;
}
return(a);
}
int gongbeishu(int a,int b)/*求两个数的最小公倍数*/
{
int gongyueshu(int a,int b);
int temp;
temp=gongyueshu(a,b);
return(a*b/temp);
}
int gys(int g[],int n)/*求n个数最大公约数*/
{
int i,m,x,y;
m=g[0];
for(i=0;i<n-1;i++)/*先求出两个数的最大公约数，再和第三个数求值直到数组循环结束*/
{
x=m;
y=g[i+1];
m=gongyueshu(x,y);
cout<<m<<endl;
}
return m;
}
int gbs(int g[],int n)/*求n个数最小公倍数*/
{
int i,m,x,y;
m=g[0];
for(i=0;i<n-1;i++)
{
x=m;
y=g[i+1];
m=gongbeishu(x,y);
cout<<m<<endl;
}
return m;
}
void main()
{
int g[N],n,i;
cout<<"请输入进行比较的数据个数："<<endl;
cin>>n;
cout<<"请输入进行比较的数据:"<<endl;
for(i=0;i<n;i++)
{
cin>>g[i];
}
cout<<"最大公约数为:"<<gys(g,n)<<endl;
cout<<"最小公倍数为:"<<gbs(g,n)<<endl;
}
int main()/*Hankson问题*/
{
int n;
cin>>n;
while(n--)
{
int count=0;
int x,a0,a1,b0,b1;
cin>>a0>>a1>>b0>>b1;
for(x=a1;x<=b1;x+=a1)
{
if(gongyueshu(x,a0)==a1&&gongbeishu(x,b0)==b1)
count++;
}
cout<<count<<endl;
}
return 0;
}
运行结果
求n个数的最大公约数和最小公倍数
Hankson问题