[数学题]HDU1108 最小公倍数


http://acm.hdu.edu.cn/showproblem.php?pid=1108
辗转相除法。
设有a,b两个数,用大的对小的取余,然后将余数与小的那个数重复取余,直到余数为0;则最后的那个除数m即为最大公约数,最小公倍数为a*b/m
[c]
#include <stdio.h>
#include <stdlib.h>

int judge(int a,int b)
{
if(a%b==0)
return b;
else
judge(b,(a%b));
}

int main()
{
//freopen("data.txt","r",stdin);
int a,b,m,n,t,max,min;
while(scanf("%d%d",&a,&b)!=EOF)
{
m=a;n=b;
if(a<b)
{
t=a;a=b;b=t;
}
max=judge(a,b);
min=m*n/max;
printf("%d %dn",min,max);
return 0;
}
[/c]

发表评论