C语言实现最大公约数与最小公倍数的相关问题
一、题目要求
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 |
二、问题分析
根据题目，我们可以了解到，x是与a0的最大公约数a1的一个倍数，同时也是与b0的最小公倍数b1的一个因数，因此，可以仅使用gcd()函数进行计算，即
|
gcd(x,a0)=a1 (x*b0)/gcd( x,b0)=b1 |
通过此式，可以采用穷举法解决本题，但是穷举法有很多弊端，我们将式子进行变式，简化算法。
由此可以得出，
|
gcd(x/a1,a0/a1)=1 gcd(b1/b0,b1/x）=1 |
此处运用了数论唯一分解定理，可以得到x/a1与a0/a1，b1/b0与b1/x均互质，以此作为判断条件，求解x。
三、算法设计
1、firsttry
2、lasttry
四、调试
五、测试
1、测试gcd()函数
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
int main(){
int a=12,b=22;
printf("a,b的最大公约数是：%d", gcd(a,b));
}
2、测试算法
#include<stdio.h>
int gcd(int a,int b) {
return b==0?a:gcd(b,a%b);
}
int main() {
int n;
int a0,a1,b0,b1;
scanf("%d",&n);
for(;n>0;){
scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
int count=0;
int j=a0/a1,k=b1/b0; //此处使用了数论的唯一分解定理 ，算法参考于网络
for(int x=1;x*x<b1;x++) //减少x穷举的时间
if(b1%x==0){
if(x%a1==0) //x是b1的一个因子，a1是x的一个因子，先进行判断 ，优化运行时间
if(gcd(x/a1,j)==1)
if(gcd(k,b1/x)==1)
count++;
int y=b1/x; //利用y判断另一半范围中b1的因子
if(x!=y)
if(y%a1==0)
if(gcd(y/a1,j)==1)
if(gcd(k,b1/y)==1)
count++;
}
printf("%d\n",count);
n--;
}
}
六、程序代码
1、firsttry
#include<stdio.h>
int gcd(int a,int b) {
return b==0?a:gcd(b,a%b);
}
int main() {
int n;
scanf("%d",&n);
for(;n>0;n--){
int a0,a1,b0,b1;
int count=0;
scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
for(int x=a1;x*x<=b1;x++){ //使用穷举法
if(gcd(x,a0)==a1&&(x*b0)/gcd(x,b0)==b1) //当x与a0的最小公约数为a1，同时与b0的最大公倍数
count++; //为b1时，则x满足条件，count+1
int y=b1/x;
if(gcd(y,a0)==a1&&(y*b0)/gcd(y,b0)==b1)
count++;
}
printf("%d\n",count);
}
}
2、lasttry
#include<stdio.h>
int gcd(int a,int b) {
return b==0?a:gcd(b,a%b);
}
int main() {
int n;
int a0,a1,b0,b1;
int count=0;
while(1){
scanf("%d",&n);
if(n<=0){
printf("\n请输入正确的组数:");
continue;
}
break;
}
printf("%d\n",n);
for(;n>0;n--){
while(1){
scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
if(a0<=0||a1<=0||b0<=0||b1<=0){
printf("\n请输入正确的数：");
continue;
}
break;
}
int j=a0/a1,k=b1/b0; //此处使用了数论的唯一分解定理 ，算法参考 //于网络
for(int x=1;x*x<b1;x++) //减少x穷举的时间
if(b1%x==0){
if(x%a1==0) //x是b1的一个因子，a1是x的一个因子 ， //先进行判断 ，优化运行时间
if(gcd(x/a1,j)==1)
if(gcd(k,b1/x)==1)
count++;
int y=b1/x; //利用y判断另一半范围中b1的因子
if(x!=y)
if(y%a1==0)
if(gcd(y/a1,j)==1)
if(gcd(k,b1/y)==1)
count++;
}
printf("%d",count);
}
}
七、运行结果
八、总结
本章的题目较为简单，因此我直接选择进行了提高要求，看到题目的第一反应就是运用穷举的方法进行，然后就有了firsttry,但是运行中也发现了一些问题，例如当a1为1，而b1特别大的时候，运行时间会非常的长，甚至超出最大时限。通过查阅了大量的资料以及参考来源于网络的算法，选用了lasttry，也就是本次作业说明中的方法，这个方法十分的简洁，运用到了算术基本定理中的定理，个人感觉很高级。