最大公约数

2022年 12月 31日 56点热度 0人点赞

最大公约数与最小公倍数

  • G.C.D: greatest common divisor, 最大公约数
  • L.C.M: least common multiple, 最小公倍数

对于 $x$, $y$ 有公式:

$$
x \times y = gcd \times lcm
$$

辗转相除法

介绍

辗转相除法, 又名欧几里德算法 (Euclidean algorithm) 乃求两个正整数之最大公因子的算法. 它是已知最古老的算法, 其可追溯至公元前 300 年前.

辗转相除法是求最大公约数的一种方法. 它的具体做法是: 用较小数除较大数, 再用出现的余数 (第一余数) 去除除数, 再用出现的余数 (第二余数) 去除第一余数, 如此反复, 直到最后余数是 0 为止. 如果是求两个数的最大公约数, 那么最后的除数就是这两个数的最大公约数. 这个和更相减损术有着异曲同工之处.

算法实现

//
// Created by duhbb on 2022/12/31.
//
#include <stdio.h>
#include <iostream>              // 输入输出
#include <vector>                // 可变长度数组
#include <unordered_map>         // hashmap
#include <stack>                 // 栈
#include <string>                // 字符串
#include <queue>                 // 队列
#include <climits>               // 极限值
#include <algorithm>             // 算法相关的
#include <cstring>

using namespace std;

int gcd(int a, int b) {
    int rem;
    while((rem = a % b) != 0) {
        a = b;
        b = rem;
    }
    return b;
}

int main() {
    printf("gcd(%d, %d) = %d\n", 2, 4, gcd(2, 4));
    printf("gcd(%d, %d) = %d\n", 3, 5, gcd(3, 5));
    printf("gcd(%d, %d) = %d\n", 15, 5, gcd(15, 5));
    printf("gcd(%d, %d) = %d\n", 4, 2, gcd(4, 2));
    return 0;
}

$a$, $b$ 的顺序不影响最后的结果.

证明

设两数为 $a$, $b$, 有 $a>b$, 用 $\gcd(a, b)$ 表示 $a$, $b$ 的最大公约数, $r=a \bmod b$ 为 $a$ 除以 $b$ 的余数, $k$ 为 $a$ 除以 $b$ 的商, 即 $a \div b=k \ldots r$. 辗转相除法即是要证明

$$
\gcd(a, b)=\gcd(b, r)
$$

第一步: 令 $c=\gcd(a, b)$, 则设 $a=m \times c$, $b=n \times c$

第二步: 根据前提可知 $r=a - k \times b=m \times c-k \times n \times c=(m-k\times n) \times c$

第三步: 根据第二步结果可知 $c$ 也是 $r$ 的因数

第四步: 可以断定 $m-k \times n$ 与 $n$ 互质.

假设 $m-k\times n=x \times d$, $n=y\times d$, 其中 $d>1$, 则

$$
\begin{align}
m&=k\times n+x\times d=k\times y \times d+x\times d=(k\times y+x) \times d\\
a&=m\times c=(k\times y+x) \times c\times d\\
b&=n\times c=y\times c \times d\\
\end{align}
$$

则 $a$ 与 $b$ 的一个公约数 $c\times d>c$, 故 $c$ 非 $a$ 与 $b$ 的最大公约数, 与前面结论矛盾), 因此 $c$ 也是 $b$ 与 $r$ 的最大公约数.

即 $a$ 与 $b$ 的余数 $r$, 余数 $r$ 也能被 $c$ 整除, 且 $c$ 是 $r$ 的最大公约数.

从而可知 $\gcd(b, r)=c$, 继而 $\gcd(a, b)=\gcd(b, r)$.

证毕.

整理自:https://blog.csdn.net/wangjiaweiwei/article/details/123040380

递归版本

/**
 * 解题思路:
 * 如果两个数为 0, 则最大公约数为 0;
 * 如果两个数可以直接相除, 则最大公约数为除数;
 * 其余情况使用辗转相除法递归
 */
#include <stdio.h>
int gcd(int m, int n) {
    if (m == 0 || n = = 0)
        return 0;
    if (m % n == 0)
        return n;      // 如果 b 能被 a 整除则 b 就是最大公约数
    else
        gcd(n, m % n); // 递归调用
}
int main() {
    int m, n, r;
    printf(" 请输入两个数:\n");
    scanf("%d %d", &m, &n);
    r = gcd(m, n);
    printf("%d 和%d 的最大公约数为:%d\n", m, n, r);
}

更相减损术

首先介绍下更相减损术的原理, 假设有两个数 $161$ 和 $63$.

  1. 我们要求这两个数的最大公因数, 不妨假定这个最大公因数为 $m$;
  2. 我们可以将较大的数 $161$ 看成 $63+98$, $63$ 与 $98$ 的和 $161$ 可以被 $m$ 整除, 其中 $63$ 也可以被 $m$ 整除, 自然 $98$ 可以被 $m$ 整除;
  3. 所以这个问题就转换为求 $98$ 和 $63$ 的最大公因数 $m$(和上面 $m$ 相等)
  4. 将 $98$ 看成 $63+35$, 其中 $63$ 可以被 $m$ 整除, 和 $98$ 也能被 $m$ 整除, 故 $35$ 也可以被 $m$ 整除;
  5. 所以问题进一步转换为求 $35$ 和 $63$ 的最大公因数 $m$(和上面 $m$ 相等)
  6. 同理转换为求 $(63-35) = 28$ 和 $35$ 的最大公因数
  7. 然后转换为求 $28$ 和 $7$ 的最大公因数
  8. 一直减呀减
  9. 后来转换为求 $7$ 和 $7$ 的最大公因数
  10. 最后转换为求 $7$ 和 $0$ 的最大公因数
  11. 输出第一个数字即可; 这就是相减损术的原理
  12. 我们发现求 $28$ 和 $7$ 的最大公约数, 一直减 $7$, 一直减$7$, 减到不能减为止. 这个不断减 $7$ 的过程就是除 $7$ 求余数 (即 $\% 7$)

这样我们可以将相减损术优化成辗转相除法, 上面给出了思考过程, 有兴趣可以百度严谨的证明过程.

原文链接:https://blog.csdn.net/weixin_43886797/article/details/85569998

辗转相减法

int measure(int a, int b) {
    while(a != b) {
        if(a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }
    return a;
}

穷举法


int measure(int x, int y) {
    int temp = 0;
    for(temp = x ; ; temp-- ) {
        if(x%temp == 0 && y%temp==0)
            break;
    }
    return temp;
}

rainbow

这个人很懒,什么都没留下

文章评论