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\) 个元素排成一列，产生的不同排列的数量为：
\[A_n^m(也可记作P_n^m)=\frac{n!}{(n-m)!}=n*(n-1)*\cdots*(n-m+1) \]组合数: 从 \(n\) 个不同的元素中取出 \(m\) 个组成一个集合（无顺序），产生的不同集合数量为：
\[C_n^m=\frac{n!}{m!(n-m)!}=\frac{n*(n-1)*\cdots*(n-m+1)}{m*(m-1)*\cdots*2*1} \]组合数性质:
- \(C_n^m=C_n^{n-m}\)
- \(C_n^m = C_{n-1}^m + C_{n-1}^{m-1}\)
- \(C_n^0+C_n^1+C_n^2+\cdots+C_n^m=2^n\)