首页 > 代码库 > 欧几里得算法及扩展算法。

欧几里得算法及扩展算法。

2024-11-26 15:50:02   203人阅读

百度百科：

欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

证明：
　　r = a mod b,  a = b * k + r;
=>   r = a - b * k;
d|a && d|b
=>(a/d - b / d * k) = r / d
=>d|r
∴ gcd(a, b) = gcd(b, a mod b);
代码
int gcd(int a, int b)
{
  return (a % b == 0 ? b : gcd(b, a % b);  
}

 

 
扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。
证明：
a*x + b*y = gcd(a, b)
b*x + (a mod b)*y = gcd(b, a mod b);
gcd(a, b) = gcd(b, a mod b)
=>a*x + b*y = b*x + (a - (a/b)*b*y)
=>a*x + b*y = a*y + b(x - a / b *y)
∴存在一组解， x = y; y = x - a / b * y;
可知xy的解基于abxy， 而当a % b == 0的时候，可以得到{x = 0, y = 1}这一组解，这就是递归边界。
利用计算机解代码是 
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
    return (a % b == 0 ? b : gcd(b, a % b));
}
void Fun(int a, int b, int &x, int &y)
{
    if(a % b == 0)
    {
        x = 0; y = 1;
        return;
    }
    Fun(b, a % b, x, y);
    int x1 = x, y1 = y;
    x = y1;
    y = x1 - a / b * y1;
    return;
}
int main()
{
    int x, y;
    int a, b;
    while(cin >> a >> b)
    {
        Fun(a, b, x, y);
        cout << "x = " << x << " y = " << y << endl;
    }
    return 0;
}

 

 
 
 

欧几里得算法及扩展算法。


联系
我们