啦啦啦


私信TA

用户名:uq_76395963979

访问量:680

签 名:

等  级
排  名 1387
经  验 2764
参赛次数 0
文章发表 5
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

解题思路:

     辗转相除法又称为欧几里德算法。这个方法大家已经都已经在数学上学过了。具体的步骤就是:用较小数除较大数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。最后的除数就是这两个数的最大公约数。举个例子就是:比如两个数字,x=453,y=36;


453%36=21;

36%21=15;

21%15=6;

15%6=3;

6%3=0;


%是取余符号,大家应该都知道吧。所以用这个算法可以求出453和36的最大公约数是3;


注意事项:




参考代码:


          

#include <stdio.h>

#include <stdlib.h>


//辗转相除


int f(int n, int m)

{

    if(m%n==0)return n;

    else f(m, n%m);

}

int main()

{


    int n, m;

    scanf("%d%d",&n, &m);

    printf("%d %d\n", f(n, m), n*m/f(n, m));

    return 0;

}


 

0.0分

0 人评分

  评论区