解题思路:
对于求两个整数的最小公倍数采用辗转相除法:
设两数为a、b(b<a),用gcd(a,b)表示a,b的最大公约数,r=a mod b 为a除以b以后的余数,k为a除以b的商,即a÷b=k.......r。辗转相除法即是要证明gcd(a,b)=gcd(b,r)。
第一步:令c=gcd(a,b),则设a=mc,b=nc
第二步:根据前提可知r =a-kb=mc-knc=(m-kn)c
第三步:根据第二步结果可知c也是r的因数
第四步:可以断定m-kn与n互质【否则,可设m-kn=xd,n=yd,(d>1),则m=kn+xd=kyd+xd=(ky+x)d,则a=mc=(ky+x)cd,b=nc=ycd,故a与b最大公约数成为cd,而非c,与前面结论矛盾】
从而可知gcd(b,r)=c,继而gcd(a,b)=gcd(b,r)。
注意事项:
参考代码:
#include<stdio.h>
int gongyue(int a,int b);
int gongbei(int a,int b);
int main()
{
int m,n;
scanf("%d%d",&m,&n);
printf("%d\n%d",gongyue(m,n),gongbei(m,n));
return 0;
}
int gongyue(int a,int b)
{
if(b==0) return a;
else return gongyue(b,a%b);
}
int gongbei(int a,int b)
{
int i=1;
while((a*i)%b!=0) i++;
return a*i;
}
0.0分
2 人评分
C语言程序设计教程(第三版)课后习题12.2 (C语言代码)浏览:852 |
C语言程序设计教程(第三版)课后习题12.5 (C语言代码)浏览:871 |
大神老白 (C语言代码)浏览:675 |
【绝对值排序】 (C语言代码)浏览:830 |
矩阵乘法 (C++代码)浏览:1657 |
A+B for Input-Output Practice (IV) (C++代码)浏览:712 |
简单的a+b (C++语言代码)浏览:894 |
求圆的面积 (C语言代码)浏览:1363 |
C语言程序设计教程(第三版)课后习题6.8 (C语言代码)浏览:797 |
C语言训练-尼科彻斯定理 (C语言代码)浏览:507 |