欧几里得算法及其扩展算法——数论

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了欧几里得算法及其扩展算法——数论，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1723字，纯文字阅读大概需要3分钟。

内容图文

欧几里得算法（gcd）：

??又名辗转相除法，是求最大公约数的算法。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。两个数的最大公约数通常写成 gcd(a, b)。
例如，计算a = 1071和b = 462的最大公约数的过程如下：
??从1071中不断减去462直到小于462（可以减2次，即商q0 = 2），余数是147： 1071 = 2 × 462 + 147. 然后从462中不断减去147直到小于147（可以减3次，即q1 = 3），余数是21： 462 = 3 × 147 + 21. 再从147中不断减去21直到小于21（可以减7次，即q2 = 7），没有余数： 147 = 7 × 21 + 0. 此时，余数是0，所以1071和462的最大公约数是21。
由此可以得到算法：

递归：

int gcd (int n, int m)
{
        if (m == 0)
           return n;
        else
           return gcd(m, n % m);
}

迭代：

int gcd(int m,int n)
{
        int t = 1;
        while(t != 0) {
            t = m % n;
            m = n;
            n = t;
        }
        return m;
}

扩展的欧几里得算法（exgcd）：

??是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式 ax+by=gcd(a,b)
例子过程展示：
用类似辗转相除法，求二元一次不定方程47x + 30y = 1的整数解。

• 47 = 30 * 1 + 17
• 30 = 17 * 1 + 13
• 17 = 13 * 1 + 4
• 13 = 4 * 3 + 1

然后，把它们改写成“余数等于”的形式。

• 17 = 47 * 1 + 30 * (-1) ?? //式1
• 13 = 30 * 1 + 17 * (-1)????//式2
• 4 = 17 * 1 + 13 * (-1)?????//式3
• 1 = 13 * 1 + 4 * (-3)

然后，倒着计算并带入式子 1， 2， 3：

• 1 = 13 * 1 + 4 * (-3)
• 1 = 13 * 1 + 【17 * 1 + 13 * (-1)】 (-3)* ????//带入式 3
• 1 = 17 * (-3) + 13 * 4
• 1 = 17 * (-3) + 【30 * 1 + 17 * (-1)】 * 4 ??// 带入式 2
• 1 = 30 * 4 + 17 * (-7)
• 1 = 30 * 4 + 【47 * 1 + 30 * (-1)】 * (-7) ??//带入式 1
• 1 = 47 * (-7) + 30 * 11

得解 x = -7，y = 11。

代码实现：

int exgcd(int a, int b, int &x, int &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int r = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - a / b * y;

    return r;
}

内容总结

以上是互联网集市为您收集整理的欧几里得算法及其扩展算法——数论全部内容，希望文章能够帮你解决欧几里得算法及其扩展算法——数论所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---