数学技巧

余数性质

$$ \begin{align} (a+b) \bmod n &= (a \bmod n + b \bmod n) \bmod n \\ (a \times b) \bmod n &= (a \bmod n \times b \bmod n) \bmod n \\ a^{b} \bmod n &= (a \bmod n)^b \bmod n \end{align} $$

同余 $$ \begin{cases} \begin{align} (a - c) &\equiv (b - d) \pmod{n} \\ (a + c) &\equiv (b + d) \pmod{n} \\ (a \times c) &\equiv (b \times d) \pmod{n} \end{align}, a \equiv b \pmod{n} \; and \; c \equiv d \pmod{n} \end{cases} $$

乘法逆元

若a × b ≡ 1 (mod  p)，且a, p互质，则b就是a的乘法逆元，记作a⁻¹，也可以叫做a在 mod  p下的倒数

有了乘法逆元就可以补充性质 $$ \frac{a}{b} \bmod p = (a \times b^{-1}) \bmod p = (a \bmod p \times b^{-1} \bmod p) \bmod p $$

求逆元

1. 扩展欧几里得算法

   欧几里得算法：有公式gcd (a, b) = gcd (b, a mod  b)，其中gcd 是最大公约数，通过辗转相除 $$ \begin{align} \gcd(a, b) &= \gcd(b, a \bmod b) \\ \gcd(b, a \bmod b) &= \gcd(a \bmod b, b \bmod (a \bmod b)) \\ &\cdots \\ \gcd(x, d) &= \gcd(d, 0) = d \end{align} $$ 当得到形如gcd (d, 0)的式子时，说明上一步中有x mod  d = 0，最大公约数为d

   扩展欧几里得算法：有公式ax + by = gcd (a, b)，x, y均为整数，有如下推论 $$ \begin{align} \because &\gcd(a, b) = \gcd(b, a \bmod b) = ax + by \\ &a \bmod b = a - \lfloor\frac{a}{b}\rfloor b \\ \therefore &\gcd(b, a \bmod b) = bx^{\prime} + (a \bmod b)y^{\prime} = ax + by \\ &bx^{\prime} + (a - \lfloor\frac{a}{b}\rfloor b)y^{\prime} = ay^{\prime} + b(x^{\prime} - \lfloor\frac{a}{b}\rfloor y^{\prime}) = ax + by \\ &x = y^{\prime} \\ &y = x^{\prime} - \lfloor\frac{a}{b}\rfloor y^{\prime} \end{align} $$ 通过辗转相除 $$ \begin{align} ax + by &= \gcd(a, b) \\ bx^{\prime} + (a \bmod b)y^{\prime} &= \gcd(b, a \bmod b) \\ &\cdots \\ dx^{\prime \prime} + 0 \times y^{\prime \prime} &= \gcd(d, 0) = d \end{align} \qquad \therefore x^{\prime \prime} = 1 \quad y^{\prime \prime} \in \mathbb{Z} $$ 根据推论往上递推最终可以求得ax + by = gcd (a, b)中的x, y $$ \begin{align} &\because a \cdot a^{-1} \equiv 1 \pmod{p} \\ &\therefore a \cdot a^{-1} + kp = 1, \; k \in \mathbb{Z} \end{align} $$ 所以当gcd (a, b) = 1，求出的x即是a在模b下的逆元

2. 费马小定理

   费马小定理：若p是质数，对应任意整数a，有a^p ≡ a (mod  p)

   欧拉定理：若正整数a, n互质，则a^φ(n) ≡ 1 (mod  n)，其中φ(n)为欧拉函数，表示在小于等于n的正整数中，与n互质的数的个数

   费马小定理是欧拉定理的特殊情况，用费马小定理求逆元 a^p − 2 ≡ a⁻¹ (mod  p) 用欧拉定理求逆元 a^{φ(n) − 1} ≡ a⁻¹ (mod  n)

快速幂

快速幂的核心在于利用二进制和位运算

计算a^b，首先将b用二进制展开得b = x₀ + 2¹x₁ + 2²x₂…, x_n ∈ {0, 1}，由此a^b = a^x₀ ⋅ a^21x₁ ⋅ a^22x₂…

b中每有一个1，代表此位置要乘a²ⁱ，否则乘1（不变），另外，有a²ⁱ ⋅ a²ⁱ = a^2i + 1

def quick_pow(base, power):
    res = 1
    while power > 0:
        if power & 1 == 1:
            res *= base
        base *= base
        power >>= 1
    return res

位运算技巧

1. 消去最后一个1：x & (x - 1)
2. 获取最后一个1：x & -x
3. 找出序列中唯一出现奇数次的数：x1 ^ x2 ^ x3 ...