• 0x30 数学知识
  • 0x33 同余
    • 概念与定理
      • 例题The Luckiest Number
    • 扩展欧几里得算法$(exgcd)$
      • 定理及概念
    • 线性同余方程
    • 高次同余方程
  • 0x34 矩阵乘法
  • 0x35 高斯消元与线性空间
    • 高斯消元
    • 线性空间
  • 0x36 组合计数
    • 基本概念
    • 组合数的求法
    • 二项式定理
    • 多重集的排列数与组合数
    • Lucas 定理
    • Catalan 数列

0x30 数学知识

0x33 同余

概念与定理

定义: 如果\(a\%m = b\%m\)，则 \(a\) 与 \(b\) 模 \(m\) 同余, \(m\) 为正整数，记作 \(a\equiv b\pmod m\)

同余类: 对于 \(\forall a \subset [0, m-1]\) ,集合 \({a+km}(k\subset Z)\) 的所有模 \(m\) 同余，余数都是 \(a\)。该集合就是一个模 \(m\) 的同余类，记为 \(\bar{a}\)。

完全剩余系: 模 \(m\) 的同余类一共有 \(m\) 个，分别为 \(\bar{1},\bar{2},\dots,\overline{m-1}\) ,是一个完全剩余系。

简化剩余系: \(1～m\) 中与 \(m\) 互质的数代表的同余类共有\(\varphi(m)\) 个，它们构成 \(m\) 的简化剩余系，例如，模 \(10\) 的简化剩余系为 \({\bar{1}, \bar{3}, \bar{7}, \bar{9}}\) 。( \(\varphi(n)\) 大小为小于 \(n\) 的所有与 \(n\) 互质的正整数个数)

若 \(a, b(1 ≤ a,b ≤ m)\) 与 \(m\) 互质， 则 \(a*b\) 与 \(m\) 也互质，也能属于 \(m\) 的简化剩余系。

费马小定理: 若 \(p\) 是质数，则对于任意整数 \(a\),有 \(a^p\equiv a\pmod p\)。

欧拉定理: 若正整数 \(a,n\) 互质，则 \(a^{\varphi(n)}\equiv 1\pmod n\)，其中 \(\varphi(n)\) 为欧拉函数。

（证明略）

其中，若 \(p\) 是一个质数，则 \(\varphi(p) = p - 1\)。

欧拉定理的推论: 若正整数 \(a,n\) 互质，则对于任意正整数 \(b\),有 \(a^b\equiv a^{b\mod \varphi(n)}\pmod n\)。

对答案取模 \(p\) 的应用技巧:

• 面对 \(a+b,a-b,a*b\) 这种算式，先对 \(a,b\) 分别对 \(p\) 取模。
• 面对乘法算式, 根据欧拉定理的推论，先将底数对 \(p\) 取模$、质数对 \(\varphi(p)\) 取模，再计算乘方。
• 特别地，当 \(a,n\) 不一定互质且 \(b>\varphi(n)\) 时，有 \(a^b\equiv a^{b\mod \varphi(n) + \varphi(n)}\pmod n\)，即意味着，即便底数 \(a\) 与 模数 \(n\) 不互质，也能把指数的规模给缩小。 （指数循环节证明）

例题The Luckiest Number

此题由欧拉函数引出一个推理:

• 满足 \(a^x\equiv1\pmod n\) 的最小的 \(x\), \(x_0\) 是 \(\varphi(n)\) 的约数。

此题启发点：

• \(x\) 个 \(8\) 连起来的数可以写作 \(8(10^x-1)/9\)，题意是求最小的 \(x\)，满足 \(L\mid 8(10^x -1)\)。设 \(d=gcd(L,8)\)，然后推导运用引理。

扩展欧几里得算法\((exgcd)\)

定理及概念

\(Bezout\) 定理:对于任意整数 \(a,b\) ,存在一对整数 \(x,y\), 满足 \(ax+by=gcd(a,b)\)。

乘法逆元:

线性同余方程

高次同余方程

0x34 矩阵乘法

0x35 高斯消元与线性空间

高斯消元

线性空间

0x36 组合计数

基本概念

加法原理: 完成一件事有 \(n\) 类方法，其中第 \(i\) 类方法包括 \(a_i\) 种不同的方法，且方法之间相互独立，则完成这件事共有 \(a_1+a_2+\ldots+a_n\) 种不同方法。

乘法原理: 完成一件事要 \(n\) 个步骤，其中第 \(i\) 个步骤有 \(a_i\) 种不同的方法，方法、步骤之间相互独立,则完成这件事共有 \(a_1*a_2*\cdots*a_n\) 种不同方法。

排列数: 从 \(n\) 个不同元素中依次取出 \(m\) 个元素排成一列，产生的不同排列的数量为：

组合数: 从 \(n\) 个不同的元素中取出 \(m\) 个组成一个集合（无顺序），产生的不同集合数量为：

组合数性质:

1. \(C_n^m=C_n^{n-m}\)
2. \(C_n^m = C_{n-1}^m + C_{n-1}^{m-1}\)
3. \(C_n^0+C_n^1+C_n^2+\cdots+C_n^m=2^n\)

组合数的求法

二项式定理

多重集的排列数与组合数

Lucas 定理

Catalan 数列