搜 索

常用数论知识

  • 333阅读
  • 2021年10月15日
  • 0评论
首页 / 正文

本篇是为了防止我偶尔健忘,整理了一些数论

欧拉函数

欧拉定理

若 $(a,m)=1$ ,则 $a^{\varphi(m)}\equiv1\ (\text{mod}\ m)$

扩展欧拉定理

$$ a^b\equiv\begin{cases} a^{b \ \text{mod}\ \varphi(p)}& (a,p)=1\\ a^b&(a,p)\not= 1,b<\varphi(p)\\ a^{b\ \text{mod}\ \varphi(p)+\varphi(p)}&(a,p)\not=1,b\geq\varphi(p) \end{cases}\quad \text{mod}\ m $$

莫比乌斯函数

$$ \begin{aligned} \mu(n)&=\begin{cases} 1&n=1\\ 0 &n 有平方因子 \\ (-1)^k&k 为本质不同质因子个数 \end{cases} \\\\ \sum_{d|n}\mu(d)&=\epsilon(n)=[n=1] \end{aligned} $$

莫比乌斯反演

$$ f(n)=\sum_{n|d}g(d)\iff g(n)=\sum_{n|d}\mu(d)f(\frac{n}{d}) $$

莫比乌斯反演扩展

对于数论函数 $f,g$ 和完全积性函数 $t$ 且 $t(1)=1$:

$$ f(n)=\sum_{i=1}^nt(i) g\bigg(\bigg\lfloor\frac{n}{i}\bigg\rfloor \bigg )\iff g(n)=\sum_{i=1}^n\mu(i)t(i) f\bigg(\bigg\lfloor\frac{n}{i}\bigg\rfloor \bigg ) $$

二项系数等式

$$ \begin{aligned} \binom nk&=\frac{n!}{k!(n-k)!}\quad 阶乘展开 \\\\ \binom rk&=\binom {r}{r-k} \quad 对称 \\\\ \binom{r}{k}&=\frac{r}{k}\binom{r-1}{k-1}\quad 吸收 / 抽出 \\\\ \binom rk&=\binom{r-1}k+\binom{r-1}{k-1}\quad 加法 / 归纳 \\\\ \binom rk&=(-1)^k\binom{k-r-1}{k}\quad 上求反 \\\\ \binom rm \binom mk&=\binom rk \binom {r-k}{m-k}\quad 三项修正 \\\\ \sum_k\binom{r}{k}x^ky^{r-k}&=(x+y)^r\quad 二项定理 \\\\ \sum_{k\leq n}\binom{r+k}{k}&=\binom{r+n+1}{n}\quad 类似求和 \\\\ \sum_{0\leq k\leq n}\binom{k}{m}&=\binom{n+1}{m+1}\quad 上求和 \\\\ \sum_k\binom r{m+k}\binom s{n-k}&=\binom{r+k}{m+n}\quad \text{Vandermondc 结合式}\\\\ \sum_{0\leq k\leq n}k^{\underline{m}}&=\frac{(n+1)^{\underline{m+1}}}{m+1}\\\\ 2^n&=\sum_{i}^{n}\binom{n}{i}\\\\ 0&=\sum_{i}^n(-1)^n\binom ni\\\\ \end{aligned} $$

斯特林数等式

第一类斯特林数

$$ \begin{aligned} {n\brack k}&=(n-1){n-1\brack k}+{n-1\brack k-1}\\\\ \sum_{k=0}^n{n\brack k}&=n!\\\\ x^\overline n&=\sum_k{n\brack k}x^k\\\\ x^\underline n&=\sum_k{n\brack k}(-1)^{n-k}x^k \end{aligned} $$

$1.$ 考虑每一个数,要么跟在剩下的数后面,要么新开一个轮换

$2.$ 考虑每一种排列对应某一个轮换的集合,所以最终一定包含所有排列

$3.$ 因为 $(x+n-1)x^k=x^{k+1}+(n-1)x^k$,带入证明即可

第二类斯特林数

$$ \begin{aligned} {n\brace k}&=k{n-1\brace k}+{n-1\brace k-1}\\\\ x^n&=\sum_k{n\brace k}x^\underline k=\sum_k{n\brace k}(-1)^{n-k}x^\overline k\\\\ \end{aligned} $$

$1.$ 考虑每一个数,要么新开一个集合,要么放进前面的集合里,有 $k$ 种方案

$2.$ 因为 $x·x^\underline k=x^{\underline{k+1}}+kx^\underline k$ 且 $x^{\underline{k+1}}=x^\underline k(x-k)$ , 后面那个只要把上升 / 下降幂拆开发现有负号

$$ \begin{aligned} \sum_k{n\brace k}{k\brack m}(-1)^{n-k}=\sum_k{n\brack k}{k\brace m}(-1)^{n-k}=[m=n] \end{aligned} $$

无标签
评论区
暂无评论
avatar