矩阵逆元一、定义设$A$是一个$n$阶方阵，若存在另一个$n$阶方阵$B$，使得$AB=BA=E$，则称方阵$A$可逆，并称方阵$B$是$A$的逆矩阵，记作$A^{-1}$二、求法1.伴随矩阵求逆法设$A=(a_{ij})_{n\times n}$，$A_{ij}$为$A$的元素$a_{ij}$的代数余子式，则矩阵$$ \left[ \begin{matrix} A_{11} & A...

自适应辛普森法一、定积分定积分是积分的一种，是函数$f(x)$在区间$[a,b]$上积分和的极限定积分的几何意义是函数的曲线上$x$的一段区间与$x$轴围成的曲边梯形的带符号面积表示为$$\int_a^b f(x)\mathrm{d}x$$由定积分的定义，若函数$f(x)$在区间$[a,b]$上可积分，则有$n$等分的特殊分法$$\lim_{n \rightarrow +\infty} \s...

素数判断一、素数的定义质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。注意 $1$ 不是素数也不是合数。二、判断一个数是否为素数由定义可得，一个数 $n$ 为素数当且仅当它只含因数 $1$ 和它本身。于是可从 $2$ 枚举到 $n-1$ 判断其是否为 $n$ 的因数。inline bool isPrime(int x){ ...

卢卡斯定理一、卢卡斯（Lucas）定理求$$C_n^m \ (\bmod \ p)$$1.定理$$ \begin{aligned} & a=a_kp^k+a_{k-1}p^{k-1}+\dots+a_1p+a_0 \\ & b=b_kp^k+b_{k-1}p^{k-1}+\dots+b_1p+b_0 \end{aligned} $$其中 $0 \le a_i,b_i \le ...

乘法逆元一、逆元的定义若 $a \cdot x \equiv 1 \ (\bmod \ p)$ 且 $(a,p)=1$ ，则称 $a$ 关于模 $p$ 的乘法逆元为 $x$ ，记为 $a^{-1}$ 。二、逆元的求法1.费马（Fermat）小定理若 $p$ 为素数，且 $(a,p)=1$ ，则有 $a^{p-1} \equiv 1 \ (\bmod \ p)$ 。由费马小定理 $$a \cd...

欧拉定理 & 费马小定理一、欧拉（Euler）定理1.定理若 $(a,m)=1$ ，则$$a^{\varphi(m)} \equiv 1 \ (\bmod \ m)$$ 其中 $\varphi(m)$ 为欧拉函数，定义为小于或等于 $m$ 的正整数中与 $m$ 互质的数的数目。2.证明：记模 $m$ 意义下的缩系（小于 $m$ 且与 $m$ 互素的正整数集合）$$R=\{x_1,x_2,\d...

欧几里得算法一、欧几里得（Euclid）算法又称辗转相除法，用于求两数最大公约数。$$(a,b)=(b,a\%b)$$代码：int gcd(int a,int b){ return b?gcd(b,a%b):a; }二、扩展欧几里得（Euclid）算法用于求解方程 $$ax+by=(a,b)$$ 的所有整数解 $(x,y)$ 。考虑 $$(a,b)=(b,a\%b)$$$\becau...