最大公约数

让第二个数比第一个小 递归实现

def pgcd(a, b)
return a if b == 0 else pgcd(b, a%b)

贝祖等式

对于两个整数 a 和 b，我们希望确定两个整数 u 和 v，使得在 d 是 a 和 b 最大公约数的情况下
有 au + bv = d。
这个计算基于一个简单结论。如果 a = qb + r、au + bv = d 与 (qb + r) u + bv = d 相关，对于 bu' +
rv' = d 有

有些问题更关心大数字的计算，因此需要返回一个大数除以一个大素数 p 的余数来确定结
果是否成立。由于 p 是素数，我们可以把它除以一个非 p 倍数的整数 a：a 和 p 互质，所以其贝
祖系数满足 au + pu = 1；因此 au 的值是 1 除以 p 求余，而 u 是 a 的倒数，所以 p 除以 a 也就是
乘以 u

def bezout(a, b):
if b == 0:
return(1, 0)
else:
u, v = bezout(b, a % b)
return(v, u - (a // b) * v)
def inv(a, p):
return bezout(a, p)[0] % p

 二项式系数C（n,k）当计算 时，分别计算 n(n - 1),…, (n - k+1) 和 k! 是有风险的，因为可能会发生容量越界的情
况。我们更倾向于使用以下结论：i 个连续整数的乘积一定包含一个能被 i 整除的元素。

def binom(n, k):
    prod = 1
    for i in range(k):
    prod = (prod * (n - i)) // (i + 1)
    return prod

在大多数问题中，计算二项式系数都需要除以一个素数 p。基于贝祖等式对系数的计算，代码
如下

def binom_modulo(n, k, p):
    prod = 1
    for i in range(k):
        prod = (prod * (n - i) * inv(i + 1, p)) % p
    return prod

快速求幂

给定 a 和 b，我们希望计算 a b 。重申一次，由于结果数值可能很大，通常会要求把算式的结果
除以给定整数 q 并求余，但这不会改变问题的本质。

简单解法会把 a 相乘 b - 1 次。但我们可以利用关系 a 2k ·a 2k = a 2k+1 来快速计算形式为 a 1 , a 2 , a 4 ,
a 8 ,…的 a 的幂。一个技巧就是把幂次 b 用二进制拆分

def fast_exponentiation(a, b, q):
    assert a >= 0 and b >= 0 and q >= 1
    p = 0  # 只用于记录
    p2 = 1 # 2 ^ p
    ap2 = a % q  # a ^ (2 ^ p)
    result = 1
    while b > 0:
        if p2 & b > 0: # b 由 a^(2^p) 拆分而来
            b -= p2
        result = (result * ap2) % q
        p += 1
        p2 *= 2
        ap2 = (ap2 * ap2) % q
    return result

这个技巧也可以用于矩阵乘法。设一个矩阵 A 和一个正整数 b，快速求幂算法能在 O(logb) 次
矩阵乘法运算内计算 A ^b

求N以内的素数

对于给定 n，我们寻找所有小于 n 的素数。“埃拉托斯特尼筛法”是实现目标的最简便方式。我
们从一个所有小于 n 的整数列表开始：首先划掉 0 和 1；然后，对于每个 p = 2, 3, 4, …, n - 1，如果 p
没有被划掉，那么它就是素数；在这种情况下，我们把 p 的所有倍数都划掉。整个过程的复杂度分

析起来很繁琐，其值是 O(nloglogn)。

下面提供的实现方法通过划掉 0、1 以及所有 2 的倍数来节省时间。在这种情况下，在对 p 进
行迭代时的步长应当是 2，从而只测试所有奇数。

def eratosthene(n):
    P = [True] * n
    answ = [2]
    for i in range(3, n, 2):
        if P[i]:
            answ.append(i)
            for j in range(2 * i, n, i):
                P[j] = False
    return answ

计算数值表达式

一般来说，问题的解决方式是通过扫描器或分词器把包含表达式的字符串分割为词汇单元流。
然后根据词汇单元，使用解析器来按照语法规则建立语法树。
但是，如果语法和算数表达式的语法类似，我们可以使用更容易实现的两个栈方法：一个栈保
存值，另一个栈保存运算符。遇到一个数值，就将其原样存入保存值的栈。对于遇到的运算符 p，
在把它加入运算符栈之前，需要执行以下操作：当运算符栈顶 q 的优先级至少和 p 相等时，我们把
q 出栈，最后两个值 a 和 b 也出栈，然后再把表达式 a q b（a 与 b 进行 q 运算的结果）的值加入数
值栈。
使用同样的方式，运算符的求值被延期处理，直到优先级规则强制要求求值

def arithm_expr_eval(cell, expr):
    if isinstance(expr, tuple):
    (left, op, right) = expr
    l = arithm_expr_eval(cell, left)
    r = arithm_expr_eval(cell, right)
    if op == '+':
        return l + r
    if op == '-':
        return l - r
    if op == '*':
        return l * r
    if op == '/':
        return l // r
    elif isinstance(expr, int):
        return expr
    else:
        cell[expr] = arithm_expr_eval(cell, cell[expr])
        return cell[expr]

语法树按照上述方法来建立。注意对括号的特殊处理：左括号总被加入运算符堆栈，而没有
其他操作；右括号让运算符与相关左括号的顶点（即以它为根的子树）组成的表达式并出栈。为
了在处理结束时彻底清空栈，我们在字符流尾部加入“;”作为表达式的结尾，并赋予它最低的优
先级。