欧几里得算法及相关扩展算法

代码演示

let logs: string[] = [];
function gcd(a, b): number {
    logs.push(`gcd(${a}, ${b})`);
    if(b) return gcd(b, a%b);
    return a;
}

const res = gcd(4, 6);
logs.push(String(res));
console.log(logs.join(' = '));
// gcd(4, 6) = gcd(6, 4) = gcd(4, 2) = gcd(2, 0) = 2
1
2
3
4
5
6
7
8
9
10
11

证明1：b 和 a % b 的最大公约数，是 a 和 b 的公约数

1. 假设b和a % b的最大公约数为c，既然c是两者的最大公约数，那么就可以得出以下结论：

2. b = k1 * c，k1代表系数，即b由多少个最大公约数相乘可以得到

3. a % b = k2 * c ，因为取模运算实际上就是尝试让a减去若干个b，直到无法再减时的余数就是结果，因此，公式等量代换为：a - k * b = k2 * c，即：a = k2 * c + k * b，又因为b = k1 * c，所以：a = k2 * c + k * k1 * c = c * (k2 + k * k1)。

4. 联立上面两个最终公式观察：

   • b = k1 * c
   • a = c * (k2 + k * k1)

   观察发现，c同时是a和b的公约数。

5. 由此证明了b和a%b的最大公约数c是a和b的公约数。

证明2：b 和 a % b 的最大公约数也是 a 和 b 的最大公约数

我们使用反证法来证明：

1. 假设b和a % b的最大公约数为d，按照证明1的结论，如果b和a % b的最大公约数d不是a和b的最大公约数的话，那么就会得出以下结论：gcd(a, b) = gcd(k1, (k2 + k * k1)) = d | d ≠ 1，因为如果d等于1就会使得c成为a和b的最大公约数，我们这里要使用反证法证明，因此，假设d≠1成立。

2. 根据条件1我们可以得到以下公式：

   • k1 = n * d，既然d是k1的最大公约数，那么k1肯定就是n倍的d
   • k2 + k * k1 = m * d ; k2 = m * d - k * k1 = m * d - k * n * d = (m - k * n) * d，

3. 结合证明1得：

   • b = k1 * c = n * d * c
   • a % b = k2 * c = (m - k * n) * d * c

   如果按照刚开始的假设：d≠1的话，那么，b和a % b的最大公约数应该是d * c，而不是c，显然，我们的假设不成立，d = 1,即a与b的最大公约数也是为c。

扩展欧几里得算法

贝祖等式

ax + by = gcd(a, b) = c，即已知a、b为整数，求一组x和y的解，使得ax + by等于a和b的最大公约数。

我们依然还是利用欧几里得算法，在递归回溯的过程中确定x和y的值

代码演示

let x = 0, y = 0;
function exGcd(a: number, b: number): number {
    if(b === 0) {
        // 由于递归到了最后一层时，x、y的值是最好确定的，此时，b为0，因此我们只需要样x为1，y为0即可
        // 因为往上一层回溯时，我们需要将x和y交换位置
        x = 1;
        y = 0;
        return a;
    }
    // 递归前，我们先交换位置
    [x, y] = [y, x];
    const r = exGcd(b, a % b);
    // 递归结束后，需要交换回来
    [x, y] = [y, x];
    // 通过x和a、b计算出y的值
    y -= Math.floor(a / b) * x;
    return r;
}

const cases = [[4, 6], [3, 5], [89, 65]];

const format = (num: number) => String(num).padStart(4);

cases.forEach(item => {
    let a = item[0], b = item[1];
    const r = exGcd(a, b);
    console.log(`${format(a)} * ${format(x)} + ${format(b)} * ${format(y)} = ${format(r)}`);
});
//    4 *   -1 +    6 *    1 =    2
//    3 *    2 +    5 *   -1 =    1
//   89 *   19 +   65 *  -26 =    1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

贝祖等式的变型

• ax % b = c => ax % b = c = gcd(a,b) = ax - kb = ax + by;其中，c可能是a和b的最大公约数或者是最大公约数的倍数

数论中的欧拉公式

欧拉公式

转换成计算机中的公式表示为：

(a ^ φ(n)) % n = 1，其中a和n互质。

那么，这个公式表达了什么意思呢？

我们知道，任意数的0次方为1，而上面的公式得出：(a ^ φ(n)) % n = 1的结论，那就意味着a^x % n是有一个循环段的，也就是而这个循环段最长就是x = φ(n);

欧拉函数

上面欧拉公式中a的指数φ(n)就是欧拉函数，这个函数求解的是：小于n且与n互质的数的数量。如：

φ(6) = 2
// 小于6且与6互质的数只有1、5，因此数量为2
1
2

代码实现

function phi(n: number): number {
    // 最小的素数为2，因此，我们从2开始不断尝试每一个数看看是不是小于n的并且与n互质的数
    // res代表小于n并且与n互质的数的数量，初始为n,
    let x = 2, res = n;
    // 如果x的平方大于n的话，那么x与n不互质，终止循环
    while(x**2 <= n) {
        // 如果n与x求模为0，说明n是k倍的x,此时会出现循环段，我们应该将这个循环段从结果中减去
        // 循环段的长度实际就是res/x
        if(n%x===0) res -= res / x;
        // 我们不断将n裁剪掉每一个循环段，以缩小范围
        while(n%x===0) n /= x;
        // 累加x
        x += 1;
    }
    // 如果循环结束后，n不是1，说明最后剩下来的n还是一个素数，我们还需要从结果中减去res/n
    if(n!==1) res -= res / n;
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

扩展练习

1071. 字符串的最大公因子

代码演示

/*
 * @lc app=leetcode.cn id=1071 lang=typescript
 *
 * [1071] 字符串的最大公因子
 *
 * https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/description/
 *
 * algorithms
 * Easy (58.67%)
 * Likes:    215
 * Dislikes: 0
 * Total Accepted:    35.2K
 * Total Submissions: 59.9K
 * Testcase Example:  '"ABCABC"\n"ABC"'
 *
 * 对于字符串 S 和 T，只有在 S = T + ... + T（T 自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
 * 
 * 返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：str1 = "ABCABC", str2 = "ABC"
 * 输出："ABC"
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：str1 = "ABABAB", str2 = "ABAB"
 * 输出："AB"
 * 
 * 
 * 示例 3：
 * 
 * 
 * 输入：str1 = "LEET", str2 = "CODE"
 * 输出：""
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 
 * 1 
 * str1[i] 和 str2[i] 为大写英文字母
 * 
 * 
 */

// @lc code=start
function gcd(a: number, b: number): number {
    if(!b) return a;
    return gcd(b, a % b);
}
function gcdOfStrings(str1: string, str2: string): string {
    // 如果两个字符串是由某个公因子拼凑而成，那么无论把str1放在前面，还是放在后面
    // 我们最终拼接而成的字符串都一定相等，因此，如果不相等，说明这两个字符串不是由
    // 公因子拼凑而成
    if(str1+str2!==str2+str1) return "";
    // 求得两个字符串的最大公约数，字符串最大公因子的长度就是两个字符串长度的最大公约数
    const r = gcd(str1.length, str2.length);
    return str1.substr(0, r);
};
// @lc code=end



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72