欧几里德算法又称辗转相除法,用于求两个数的最大公约数。

其实我们需要知道的是一个公式:gcd(a,b) = gcd(b,a%b)

现在我们来举个例子模拟一下:求gcd(48,30)

步骤:

48 = 30 * 1 + 18

30 = 18 * 1 + 12

18 = 12 * 1 + 6

12 = 6 * 2 + 0

那么,gcd(48,30) = 6

我们可以写两种形式的辗转相除:递归和非递归。

递归的模板:

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

可以优化如下:

int gcd(int a,int b)
{
     return b ? gcd(b,a%b) : a;
}

非递归的模板:


int Gcd(int a, int b) { while(b != 0) {   int r = b;   b = a % b;   a = r; } return a; }

然后求两个数的最小公倍数就是a*b/gcd(a,b);

0
Posted in ACM

Leave a Comment:

电子邮件地址不会被公开。