数论

目录

• 欧几里得算法
• 最大公约数与最小公倍数
• 互素
• 扩展欧几里得

欧几里得算法

用于计算两个数的最大公约数，即gcd(m,n)

也就是初中数学的辗转相除法

# py自带gcd和lcm
from math import gcd,lcm

对于给定的值：0 ≤ m < n 计算 gcd(m, n)，可以用到以下递归式：

$gcd(0, n) = n$

gcd(m, n) = gcd(n \bmod m), m > 0

时间复杂度：O(log n)

同样还有根相减损法,即$gcd(m,n)=gcd(m-n,n)$,但是除非m,n较为相近且较大,否则远不如取余下降的快

最小公倍数lcm(m,n)=(m×n)/gcd(m,n),为了防止溢出通常先除再乘^[1]

最大公约数与最小公倍数

• 最大公约数：能整除两者的最大整数，即：gcd(m, n) = max{k | k|m & k|n} 特别地,我们约定gcd(0, n)= n, gcd(n, 0) = 0 (常作为递归边界)
• 最小公倍数：lcm(m, n) = min{k | k > 0, m|k & n|k}

互素

• 两个整数互素（既约）的定义：若 $\gcd(a_1,a_2)=1$ ，则称 $a_1$ 和 $a_2$ 互素（既约）
• 多个整数互素（既约）的定义：若 $\gcd(a_1,\ldots,a_k)=1$ ，则称 $a_1,\ldots,a_k$ 互素（既约）
• 多个整数互素，不一定两两互素。例如 $6$ 、 $10$ 和 $15$ 互素，但是任意两个都不互素

扩展欧几里得

"""
扩展欧几里得用于求出ax+by=gcd(a,b)的一组特解
通解即为 x'=x+k*b/(gcd(a,b)) y'=y-k*a/(gcd(a,b))

同时显然知道扩展欧几里得后,裴蜀定理的正确性自然一目了然

>>> exgcd(3,10)
    (1, -3, 1)
"""

def exgcd(a, b):
    if b==0: return a,1,0
    d, x, y = exgcd(b, a % b)
    return d, y, x - (a // b) * y

---

1. python虽然有高精度无需担心溢出,但是高精度运算常数还是比较大 ↩︎