辗转相除法-白红宇

辗转相除法

阅读量：3905 次

发布时间：2019-05-23

本文共 1006 字，大约阅读时间需要 3 分钟。

最近闲来无事，把之前学过的复习一下，什么叫辗转相除法呢（以下来自百度百科）

辗转相除法，又名（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

从以上的描述中，我们可以把代码写出来。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;int gcd (int a,int b){    return b==0?  a:gcd (b,a%b);}int main(){    int a,b;    scanf("%d %d",&a,&b);    printf("%d\n",gcd(a,b));    return 0;}

下面看一个例子：

链接：

来源：牛客网

题目描述

给定两个正整数a,b,求a,b的最小公倍数。（即[a,b]）

输入描述:

两个整整数,a,b

输出描述:

一个正整数，表示[a,b]

说明

对于输入输出的所有数据，保证不超过unsigned long long(18446744073709551615)

我们都知道最小公倍数为两个数之乘然后除以最大公约数。但由于此题的说明限制，所以应该先除再乘。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;unsigned long long int  gcd (unsigned long long int a,unsigned long long int b){    return b==0? a:gcd (b,a%b);}int main(){    unsigned long long int a,b;    scanf("%llu%llu",&a,&b);    printf("%llu\n",a/gcd(a,b)*b);    return 0;}

转载地址：http://sjaen.baihongyu.com/

你可能感兴趣的文章