【学习笔记】数论—常见定理、结论、性质汇总

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

【学习笔记】数论—常见定理、结论、性质汇总

作者：

Xing_Ling , 2020-06-20 17:42:41 , 所有人可见 , 阅读 2477

20

37

# **【学习笔记】数论、数学—常见定理、结论、性质汇总**

$\text{欢迎补充(*^▽^*)}$ ## **〇：【不知道放哪儿好的内容】** ### **1.【和式】** #### **【推导结论】** -

$\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$ -

$\sum_{i=1}^{n}i^{2}=\frac{n(n+1)(2n+1)}{6}$ -

$\sum_{i=1}^{n}i^{3}=\left(\frac{n(n+1)}{2}\right)^{2}$ ### **2.【下降幂、上升幂】** #### **【基本性质、定理】** -

$x^{\underline{n}}=(x-1)^{\underline{n-1}}x=\frac{(x)!}{(x-n)!}=\prod_{i=x-n+1}^{x} i$

$(x^{\underline{0}}=1)$ -

$x^{\overline{n}}=(x+1)^{\overline{n-1}}x=\frac{(x+n-1)!}{(x-1)!}=\prod_{i=x}^{x+n-1} i$

$(x^{\overline{0}}=1)$ #### **【推导结论】** -

$x^{\underline{n}}=(-1)^n(-x)^{\overline{n}}$ -

$x^{\overline{n}}=(-1)^n(-x)^{\underline{n}}$ -

$x^{\underline{n}}=A_{x}^{n}$ -

$x^{\overline{n}}=A_{x+n-1}^{n}$ ### **3.【三角函数】** #### **【基本性质、定理】** ##### **(1).【函数基本关系】** -

$\tan \alpha=\frac{\sin \alpha}{\cos \alpha}$ -

$\cot \alpha=\frac{\cos \alpha}{\sin \alpha}$ -

$\sin \alpha\csc \alpha=1$ -

$\cos \alpha\sec \alpha=1$ -

$\tan \alpha\cot \alpha=1$ -

$\sin^{2}\alpha+\cos^{2}\alpha=1$ -

$\sec^{2}\alpha-\tan^{2}\alpha=1$ -

$\csc^{2}\alpha-\cot^{2}\alpha=1$ ##### **(2).【秀导公式】** -

$\sin(-\alpha)=-\sin \alpha$ -

$\cos(-\alpha)=\cos \alpha$ -

$\tan(-\alpha)=-\tan \alpha$ -

$\cot(-\alpha)=-\cot \alpha$ -

$\sin(\pi+\alpha)=-\sin \alpha$ -

$\cos(\pi+\alpha)=-\cos \alpha$ -

$\tan(\pi+\alpha)=\tan \alpha$ -

$\cot(\pi+\alpha)=\cot \alpha$ -

$\sin(\pi-\alpha)=\sin \alpha$ -

$\cos(\pi-\alpha)=-\cos \alpha$ -

$\tan(\pi-\alpha)=-\tan \alpha$ -

$\cot(\pi-\alpha)=-\cot \alpha$ -

$\sin(\frac{1}{2}\pi-\alpha)=\cos \alpha$ -

$\cos(\frac{1}{2}\pi-\alpha)=\sin \alpha$ -

$\tan(\frac{1}{2}\pi-\alpha)=\cot \alpha$ -

$\cot(\frac{1}{2}\pi-\alpha)=\tan \alpha$ ##### **(3).【和角公式】** -

$\sin(\alpha+\beta)=\sin \alpha\cos \beta+\cos \alpha\sin \beta$ -

$\sin(\alpha-\beta)=\sin \alpha\cos \beta-\cos \alpha\sin \beta$ -

$\cos(\alpha+\beta)=\cos \alpha\cos \beta-\sin \alpha\sin \beta$ -

$\cos(\alpha-\beta)=\cos \alpha\cos \beta+\sin \alpha\sin \beta$ -

$\tan(\alpha+\beta)=\frac{\tan \alpha+\tan \beta}{1-\tan \alpha\tan \beta}$ -

$\tan(\alpha-\beta)=\frac{\tan \alpha-\tan \beta}{1+\tan \alpha\tan \beta}$ ##### **(4).【积化和差】** （同

$\cos$ 异

$\sin$ ，

$\sin$

$\sin$ 负负） -

$\cos \alpha\cos \beta=\frac{1}{2}[\cos(\alpha+\beta)+\cos(\alpha-\beta)]$ -

$\sin \alpha\sin \beta=-\frac{1}{2}[\cos(\alpha+\beta)-\cos(\alpha-\beta)]$ -

$\sin \alpha\cos \beta=\frac{1}{2}[\sin(\alpha+\beta)+\sin(\alpha-\beta)]$ -

$\cos \alpha\sin \beta=\frac{1}{2}[\sin(\alpha+\beta)-\sin(\alpha-\beta)]$ ##### **(5).【和差化积】** -

$\sin \alpha+\sin \beta=2\sin(\frac{\alpha+\beta}{2})\cos(\frac{\alpha-\beta}{2})$ -

$\cos \alpha+\cos \beta=2\cos(\frac{\alpha+\beta}{2})\cos(\frac{\alpha-\beta}{2})$ -

$\sin \alpha-\sin \beta=2\cos(\frac{\alpha+\beta}{2})\sin(\frac{\alpha-\beta}{2})$ -

$\cos \alpha-\cos \beta=-2\sin(\frac{\alpha+\beta}{2})\sin(\frac{\alpha-\beta}{2})$ -

$\tan \alpha+\tan \beta=\frac{\sin(\alpha+\beta)}{\cos \alpha\cos \beta}$ ##### **(6).【倍角公式】** -

$\sin 2\alpha=2\sin \alpha\cos \alpha$ -

$\cos 2\alpha=\cos^2 \alpha-\sin^2 \alpha=2\cos^2 \alpha-1=1-2\sin^2 \alpha$ -

$\tan 2\alpha=\frac{2\tan \alpha}{1-\tan^2 \alpha}$ ##### **(7).【半角公式】** -

$\sin \frac{\alpha}{2}=\pm\sqrt{\frac{1-\cos \alpha}{2}}$ -

$\cos \frac{\alpha}{2}=\pm \sqrt{\frac{1+\cos \alpha}{2}}$ -

$\tan \frac{\alpha}{2}=\pm \sqrt{\frac{1-\cos \alpha}{1+\cos \alpha}}$ -

$\tan \frac{\alpha}{2}=\frac{1-\cos \alpha}{\sin \alpha}=\frac{\sin \alpha}{1+\cos \alpha}$ ##### **(8).【万能公式】** -

$\sin \alpha=\frac{2\tan \frac{\alpha}{2}}{1+\tan^{2} \frac{\alpha}{2}}$ -

$\cos \alpha=\frac{1-\tan^{2} \frac{\alpha}{2}}{1+\tan^{2} \frac{\alpha}{2}}$ -

$\tan \alpha=\frac{2\tan \frac{\alpha}{2}}{1-\tan^{2} \frac{\alpha}{2}}$ ##### **(9).【正弦定理、余弦定理】** -

$\frac{a}{\sin A}=\frac{b}{\sin B}=\frac{c}{\sin C}=2 R$ （其中

$R$ 为

$\Delta ABC$ 外接圆半径） -

$\cos A=\frac{b^{2}+c^{2}-a^{2}}{2bc}$ -

$\cos B=\frac{a^{2}+c^{2}-b^{2}}{2ac}$ -

$\cos C=\frac{a^{2}+b^{2}-c^{2}}{2ab}$ ##### **(10).【常见反三角函数】** -

$\arcsin \alpha+\arccos \alpha=\frac{\pi}{2}$ ### **4.【单位根】** #### **【基本性质、定理】** -

$\omega_{n}^{k}=\cos(\frac{2\pi k}{n})+\sin(\frac{2\pi k}{n})i$ -

$\omega_{n}^{k}=g^{\frac{k(P-1)}{n}}\mod P$

$(P=k2^{t}+1,P\in \{Prime\})$ #### **【推导结论】** -

$\omega_{n}^{k}=(\omega_{n}^{1})^{k}$ -

$\omega_{n}^{j}\omega_{n}^{k}=\omega_{n}^{j+k}$ -

$\omega_{2n}^{2k}=\omega_{n}^{k}$ -

$\omega_{n}^{(k+n/2)}=-\omega_{n}^{k}$

$(n$ 为偶数

$)$ -

$\sum_{i=1}^{n-1}\omega_{n}^{i}=0$ ------------ ## **一：【基本数论、数学知识】** ### **1.【斐波那契数列（Fibonacci）】** #### **【基本性质、定理】** -

$fib_{n}=\begin{cases}0&n=0\\ 1&n=1\\ fib_{n-1}+fib_{n-2}&n>1\end{cases}$ [【模板】](https://www.luogu.com.cn/problem/P1962) #### **【推导结论】** -

$\sum_{i=1}^{n}{f_{i}}=f_{n+2}-1$ -

$\sum_{i=1}^{n}{f_{2i-1}}=f_{2n}$ -

$\sum_{i=1}^{n}{f_{2i}}=f_{2n+1}-1$ -

$\sum_{i=1}^{n}{(f_{n})^2}=f_{n}f_{n+1}$ -

$f_{n+m}=f_{n-1}f_{m-1}+f_{n}f_{m}$ -

$(f_{n})^2=(-1)^{(n-1)}+f_{n-1}f_{n+1}$ -

$f_{2n-1}=(f_{n})^2-(f_{n-2})^2$ -

$f_{n}=\frac{f_{n+2}+f_{n-2}}{3}$ -

$\frac{f_{i}}{f_{i-1}} \approx \frac{\sqrt{5}-1}{2} \approx 0.618$ -

$f_{n}=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}}{\sqrt{5}}$ [【证明】](https://www.luogu.com.cn/blog/lx-2003/generating-function) ### **2.【最大公约数（GCD）和最小公倍数（LCM）】** #### **【基本性质、定理】** -

$\gcd(a,b)=\gcd(b,a-b)$

$(a>b)$ -

$\gcd(a,b)=\gcd(b,a \mod b)$ -

$\gcd(a,b)\operatorname{lcm}(a,b)=ab$ #### **【推导结论】** -

$k | \gcd(a,b) \iff k|a$ 且

$k|b$ -

$\gcd(k,ab)=1 \iff \gcd(k,a)=1$ 且

$\gcd(k,b)=1$ -

$(a+b)\mid ab\Longrightarrow \gcd(a,b)\neq 1$ [【例题】](https://www.luogu.com.cn/problem/P4466) - 在

$Fibonacc$ 数列中求相邻两项的

$\gcd$ 时，**辗转相减**次数等于**辗转相除**次数。 -

$\gcd\left(fib_{n},fib_{m}\right)=fib_{\gcd(n,m)}$ [【证明】](https://blog.csdn.net/alan_cty/article/details/73928751) ### **3.【裴蜀（Bézout）定理】** #### **【基本性质、定理】** - 设

$a,b$ 是不全为零的整数，则存在整数

$x,y$ , 使得

$ax+by=\gcd(a,b)$ -

$\gcd(a,b)|d \iff \exists x,y\in\mathbb{Z},ax+by=d$ #### **【推导结论】** - 设不定方程

$ax+by=\gcd(a,b)$ 的一组特解为

$\begin{cases}x=x_0\\ y=y_0\end{cases}$ ，则

$ax+by=c$

$(\gcd(a,b)|c)$ 的通解为

$\begin{cases}x=\frac{c}{\gcd(a,b)}x_0+k\frac{b}{\gcd(a,b)}\\ y=\frac{c}{\gcd(a,b)}y_0-k\frac{a}{\gcd(a,b)}\end{cases}(k\in\mathbb{Z})$ 。[【模板】](https://www.luogu.com.cn/problem/P5656) -

$\forall a,b,z\in\mathbb{N^{*}},\gcd(a,b)=1,$

$\exists x,y\in\mathbb{N^{}},$

$ax+by=ab-a-b+z$ [【例题】](https://www.luogu.com.cn/problem/P3951) ### **4.【欧拉函数】** #### **【基本性质、定理】** -

$\varphi(x)=x\prod_{i=1}^{n}(1-\frac{1}{p_{i}}),$ 其中

$p_i$ 为

$x$ 的质因子，

$n$ 为

$x$ 的质因子个数 -

$\gcd(a,b)=1\Longrightarrow \varphi(ab)=\varphi(a)\varphi(b)$ （欧拉函数是积性函数） #### **【推导结论】** -

$p>2 \Longrightarrow [\varphi(p)\mod 2=0]$ -

$p\in\{Prime\} \Longrightarrow \varphi(p^{k})=p^{k}-p^{k-1}$ -

$\sum_{i=1}^{n}i[gcd(i,n)=1]=\frac{n\varphi(n)+[n=1]}{2}$ [【例题】](https://www.luogu.com.cn/problem/SP5971) -

$f(n)=\sum_{i=1}^{n}[\gcd(i,k)=1]=\frac{n}{k}\varphi(k)+f(n\mod k)$ ### **5.【同余运算】** #### **【基本性质、定理】** -

$\begin{cases}a\equiv b(\bmod m)\\ c\equiv d(\bmod m)\end{cases}\Longrightarrow a+c\equiv b+d(\bmod m)$ -

$\begin{cases}a\equiv b(\bmod m)\\ c\equiv d(\bmod m)\end{cases}\Longrightarrow a-c\equiv b-d(\bmod m)$ -

$a\equiv b(\bmod m)\Longrightarrow ak\equiv bk(\bmod m)$ -

$ka\equiv kb(\bmod m),\gcd(k,m)=1\Longrightarrow a\equiv b(\bmod m)$ ### **6.【费马小定理及其扩展】** #### **【基本性质、定理】** -

$P\in\{Prime\},P\nmid a\Longrightarrow a^{P-1}=1(\bmod P)$ #### **【推导结论】** - 对于任意多项式

$F(x)=\sum_{i=0}^{\infty}a_i x^i$ （

$a_i$ 对一个质数

$P$ 取模），若满足

$a_{0}\equiv 1(\bmod P)$ ，则

$\forall n\leqslant P,F^{P}(x)\equiv 1(\bmod x^{n})$ 。[【例题】](https://www.luogu.com.cn/problem/P5245) ### **7.【欧拉定理及其扩展】** #### **【基本性质、定理】** -

$\gcd(a,m)=1\Longrightarrow a^{\varphi(m)}\equiv 1(\bmod m)$ -

$\gcd(a,m)=1\Longrightarrow a^{b} \equiv a^{b\mod \varphi(m)}(\bmod m)$ -

$b>\varphi(m)\Longrightarrow a^{b} \equiv a^{b\mod \varphi(m)+\varphi(m)}(\bmod m)$ [【例题】](https://www.luogu.com.cn/problem/P5091) #### **【推导结论】** -

$\exists x\in N^{*},a^x=1(\bmod m)$

$\iff$

$\gcd(a,m)=1$ [【证明】](https://www.cnblogs.com/Xing-Ling/p/13219900.html) [【例题】](https://www.luogu.com.cn/problem/P1587) ### **8.【孙子定理/中国剩余定理（CRT）及其扩展】** #### **【基本性质、定理】** - 若

$m_1,m_2...m_k$ 两两互素，则同余方程组

$\begin{cases}x\equiv a_{1}\left(\bmod m_{1}\right)\\ x\equiv a_{2}\left(\bmod m_{2}\right)\\ \vdots\\ x\equiv a_{k}\left(\bmod m_{k}\right)\end{cases}$ 有唯一解为：

$x=\sum_{i=1}^{k}a_iM_iM_i^{-1},$ 其中

$M_i=\prod_{j\neq i}m_j$ 。[【模板】](https://www.luogu.com.cn/problem/P1495) ### **9.【佩尔（Pell）方程】** #### **【基本性质、定理】** - 形如

$x^2-Dy^x=1$

$(D\in\mathbb{N^{*}}\text{且为非平方数})$ 的方程被称为第一类佩尔方程。设它的一组最小正整数解为

$\begin{cases}x=x_0\\ y=y_0\end{cases},$ 则其第

$n$ 个解满足：

$x_n+\sqrt{D}y_n=(x_0+\sqrt{D}y_0)^{n+1},$ 递推式为

$\begin{cases}x_n=x_0x_{n-1}+Dy_0y_{n-1}\\ y_n=x_0y_{n-1}+y_0x_{n-1}\end{cases}$ 。[【例题】](https://www.luogu.com.cn/problem/UVA138) - 形如

$x^2-Dy^x=-1$

$(D\in\mathbb{N^{*}}\text{且为非平方数})$ 的方程被称为第二类佩尔方程。设它的一组最小正整数解为

$\begin{cases}x=x_0\\ y=y_0\end{cases},$ 则其第

$n$ 个解满足：

$x_n+\sqrt{D}y_n=(x_0+\sqrt{D}y_0)^{2n+1}$ 。递推式略。 ### **10.【勾股方程/勾股数组】** #### **【基本性质、定理】** - 方程

$x^2+y^2=z^2$ 的正整数通解为

$\begin{cases}x=k(u^2-v^2)\\ y=2kuv\\ z=k(u^2+v^2)\end{cases}(u,v\in\{Prime\},k\in\mathbb{N^{*}}),$ 且均满足

$\gcd(x,y,z)=k$ 。 -------- ## **二：【组合数学】** ### **1.【排列与组合数】** #### **【基本性质、定理】** -

$A_{n}^{m}=\frac{n!}{(n-m)!}$ 【排列】 -

$C_{n}^{m}=\frac{A_{n}^{m}}{m!}=\frac{n!}{m!(n-m)!}$ 【组合】 -

$C_{n}^{m}=C_{n}^{n-m}$ 【对称公式】 -

$C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}$ 【加法公式】 -

$C_{n}^{m}=\frac{n}{m}C_{n-1}^{m-1}$ 【吸收公式】 -

$C_{n}^{m}=(-1)^{m}C_{m-n-1}^{m}$ 【上指标反转】 -

$\sum_{i=0}^{m}C_{n+i}^{i}=C_{n+m+1}^{m}$ 【平移求和】 -

$\sum_{i=0}^{k}C_{n}^{i}C_{m}^{k-i}=C_{n+m}^{k}$ 【范德蒙德卷积】 -

$C_{n}^{k}C_{k}^{m}=C_{n}^{m}C_{n-m}^{k-m}$ #### **【推导结论】** -

$ij=C_{i+j}^{2}-C_{i}^{2}-C_{j}^{2}$ -

$\sum_{i=0}^{n}C_{n-i}^{i}=fib_{n+1}$ -

$\sum_{i=0}^{n}C_{i}^{m}=C_{n+1}^{m+1}$ （平移求和） -

$\sum_{i=0}^{n}(C_{n}^{i})^{2}=C_{2n}^{n}$ （范德蒙德卷积） -

$\sum_{i=0}^{n}(-1)^{n-i}C_{n}^{i}C_{i}^{m}=[m=n]$ （可用其证明二项式反演） -

$\sum_{i=0}^{n}(-1)^{i-m}C_{n}^{i}C_{i}^{m}=[m=n]$ （可用其证明二项式反演） ### **2.【卢卡斯定理】** #### **【基本性质、定理】** -

$C_{n}^{m}=C_{\lfloor\frac{n}{p}\rfloor}^{\lfloor\frac{m}{p}\rfloor}C_{n\mod p}^{m\mod p}$

$(p\in\{Prime\})$ [【模板】](https://www.luogu.com.cn/problem/P3807) ### **3.【库默尔定理】** #### **【基本性质、定理】** -

$\forall m,n\in\{\mathbb{Z}\},P\in\{Prime\},$

$C_{m+n}^m$ 含

$P$ 的幂次等于

$m+n$ 在

$P$ 进制下的进位次数。[【例](https://www.luogu.com.cn/problem/CF582D) [题】](http://www.51nod.com/Challenge/Problem.html#problemId=1569) ### **4.【牛顿二项式定理】** #### **【基本性质、定理】** -

$(x+y)^{n}=\sum_{i=0}^{n}C_{n}^{i}x^{n-i}y^i$ #### **【推导结论】** -

$\sum_{i=0}^{n}C_n^{i}=2^n$ -

$\sum_{i=0}^{n}iC_n^{i}=n2^{n-1}$ -

$\sum_{i=0}^{n}i^2C_n^{i}=n(n+1)2^{n-1}$ ### **5.【广义牛顿二项式定理】** #### **【基本性质、定理】** -

$C_{r}^{n}=\begin{cases}0&n<0,r\in\mathbb{R}\\ 1&n=0,r\in\mathbb{R}\\ \frac{r(r-1)\cdots(r-n+1)}{n!}&n>0,r\in\mathbb{R}\end{cases}$ -

$(1+x)^{-n}=\sum_{i=0}^{\infty}C_{-n}^{i}x^{i}=\sum_{i=0}^{\infty}(-1)^iC_{n+i-1}^{i}x^i$ -

$(x+y)^{\alpha}=\sum_{i=0}^{\infty}C_{\alpha}^{i}x^{\alpha-i}y^i$

$(x,y,\alpha\in\mathbb{R}\ \text{且}\ |\frac{x}{y}|<1)$ [【证明】](https://www.cnblogs.com/Asika3912333/p/11406614.html) ### **6.【卡特兰数 (Catalan)】** #### **【基本性质、定理】** -

$cat_{n}=\begin{cases}1&n=0\\ \sum_{i=0}^{n-1}cat_{i}cat_{n-i-1}&n>0\end{cases}$ [【模板

$1$ 】](https://www.luogu.com.cn/problem/P3200) [【模板

$2$ 】](https://www.luogu.com.cn/problem/P2532) #### **【推导结论】** -

$cat_{n}=C_{2n}^n-C_{2n}^{n+1}=\frac{C_{2n}^{n}}{n+1}$ [【感性理解】](https://www.cnblogs.com/silentEAG/p/10439166.html) [【生成函数严格证明】](https://www.luogu.com.cn/blog/lx-2003/generating-function) ### **7.【斯特林数 (Stirling)】** #### **【基本性质、定理】** -

$s_{n}^{m}=s_{n-1}^{m-1}+(n-1)s_{n-1}^{m}$

$(s_{n}^{n}=1,s_{n}^{0}=0^{n})$ 【第一类斯特林数】 -

$S_{n}^{m}=S_{n-1}^{m-1}+mS_{n-1}^{m}$

$(S_{n}^{n}=1,S_{n}^{0}=0^{n})$ 【第二类斯特林数】[【模板】](https://www.luogu.com.cn/problem/CF568B) [【例题】](https://www.luogu.com.cn/problem/P6620) -

$S_{n}^{m}=\frac{\sum_{i=0}^{m}(-1)^{m-i}C_{m}^{i}i^{n}}{m!}=\sum_{i=0}^{m} \frac{(-1)^{m-i}}{(m-i)!}\frac{i^{n}}{i !}$ [【模板】](https://www.luogu.com.cn/problem/P5395) #### **【推导结论】** -

$n!=\sum_{i=0}^{n}s_{n}^{i}$ -

$x^{\overline{n}}=\sum_{i=0}^{n}s_{n}^{i}x^i$ -

$x^{\underline{n}}=\sum_{i=0}^{n}s_{n}^{i}x^i(-1)^{n-i}$ -

$x^n=\sum_{i=0}^{x,n}S_{n}^{i}x^{\underline{i}}$ -

$x^{n}=\sum_{i=0}^{x,n}S_{n}^{i}x^{\overline{i}}(-1)^{n-i}$ -

$\sum_{i=1}^{n}S_{n}^{i}s_{i}^{m}=\sum_{i=0}^{n}s_{n}^{i}S_{i}^{m}$ -

$\sum_{i=0}^{n} i^{k}=\sum_{j=0}^{n}j!S_{k}^{j}C_{n+1}^{j+1}$ -

$\sum_{i=1}^{n}C_{n}^{i}i^{k}=\sum_{j=0}^{k} S_{k}^{j}2^{n-j}\frac{n!}{(n-j)!}$ [【例题】](https://www.luogu.com.cn/problem/CF932E) ### **8.【贝尔数 (Bell)】** #### **【基本性质、定理】** -

$B_n=\sum_{i=1}^{n}S_{n}^{i}$

$(B_0=1)$ [【模板】](https://www.luogu.com.cn/problem/CF568B) -

$B_{n}=\sum_{i=0}^{n-1}C_{n-1}^{i}B_{i}$ [【模板】](https://www.luogu.com.cn/problem/CF568B) ### **9.【Polya 定理】** #### **【基本性质、定理】** -

$ans=\frac{\sum_{i=1}^{n}m^{k_{i}}}{n}$ [【理解】](https://oldcat.huix.cc/2020/03/polya.html) ### **10.【经典容斥原理】** #### **【推导结论】** -

$f(i)=\sum\limits_{j=i}^{n}(-1)^{j-i}C_{j}^{i}g(j)$

$=g(i)-\sum\limits_{j=i+1}C_{j}^{i}f(j)$ （

$f(i)$ 为恰好

$i$ 个满足"balabala"的方案数，

$g(i)$ 为钦定

$i$ 个满足"balabala“其他随意的方案数）[【例题】](https://www.luogu.com.cn/problem/P3298) [【例题】](https://www.luogu.com.cn/problem/P4859) [【例题】](https://www.luogu.com.cn/problem/P4491) [【例题】](https://www.luogu.com.cn/problem/P6478) ### **11.【生成函数】** #### **【推导结论】** ##### **(1).【常用普通生成函数 (OGF) 收敛性式】** -

$\sum_{i=0}^{\infty}x^i=\frac{1}{1-x}$ -

$\sum_{i=0}^{\infty}a^ix^i=\frac{1}{1-ax}$ -

$\sum_{i=0}^{\infty}(i+1)x^i=\frac{1}{(1-x)^2}$ -

$\sum_{i=0}^{\infty}C_{n}^{i}x^i=(1+x)^n$ -

$\sum_{i=0}^{\infty}C_{n+i-1}^{i}x^i=\frac{1}{(1-x)^n}$ -

$\sum_{i=0}^{\infty}fib_{i}x^i=\frac{x}{1-x-x^2}$ （斐波那契数） -

$\sum_{i=0}^{\infty}(\sum_{j=0}^{i}fib_{j})x^i=\frac{x}{(1-x)(1-x-x^2)}$ （斐波那契数列前缀和） -

$\sum_{i=0}^{\infty}cat_{i}x^i=\frac{1-\sqrt{1-4x}}{2x}$ （卡特兰数） ##### **(2).【常用指数生成函数 (EGF) 收敛性式】** -

$\sum_{i=0}^{\infty}\frac{x^i}{i!}=e^x$ -

$\sum_{i=0}^{\infty}\frac{x^{2i}}{(2i)!}=\frac{e^x+e^{-x}}{2}$ -

$\sum_{i=0}^{\infty}\frac{x^{2i+1}}{(2i+1)!}=\frac{e^x-e^{-x}}{2}$ -

$\sum_{i=0}^{\infty}B_{i}\frac{x_{i}}{i!}=e^{e^{x}-1}$ （贝尔数） ------------ ## **三：【各种反演】** ### **1.【欧拉反演】** #### **【基本性质、定理】** -

$\sum_{d|n}\varphi(d)=n$ （即

$\varphi\ast 1=\operatorname{id}$ ） [【证明】](https://www.cnblogs.com/Xing-Ling/p/11988194.html) #### **【推导结论】** -

$\gcd(i,j)=\sum_{d|i,d|j} \varphi(d)$ -

$\sum_{i=1}^{n} \sum_{j=1}^{n} \gcd(i,j)=$

$\sum_{d=1}^{n}d\left(2\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}{\varphi(i)}-1\right)$ [【例题（

$9$ 倍经验）】](https://www.luogu.com.cn/discuss/show/167756) -

$\sum_{i=1}^{n} \sum_{j=1}^{m} \gcd(i,j)=$

$\sum_{d=1}^{n} \varphi(d) \lfloor\frac{n}{d}\rfloor \lfloor\frac{m}{d}\rfloor$ [【例题】](https://www.luogu.com.cn/problem/P2398) -

$\prod_{i=1}^{n} \prod_{j=1}^{n} \left(\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}\right)=$

$\frac{(n!)^{2n}}{\left(\prod_{d=1}^{n} d^{\left(2 S_{\varphi}(\lfloor\frac{n}{a}\rfloor)-1\right)}\right)^{2}}$ [【例题】](https://www.luogu.com.cn/problem/P5221) ### **2.【狄利克雷卷积 (Dirichlet) 与莫比乌斯反演 (Mobius) 】** #### **【基本性质、定理】** -

$(f \ast g)(n)=\sum_{d | n} f(d) g(\frac{n}{d})=$ -

$\sum_{d|n} \mu(d)=\epsilon(n)$ （即

$\mu\ast1=\epsilon$ ） -

$f(n)=\sum_{d | n} g(d) \Longrightarrow$

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

$f=g\ast1 \Longrightarrow g=f\ast\mu$ ） -

$f(n)=\sum_{n | d} g(d) \Longrightarrow$

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

$f(k)=\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} g(dk) \Longrightarrow$

$g(k)=\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} \mu(d) f(dk)$ #### **【推导结论】** ##### **(1).【GCD 和 LCM】** -

$[\gcd(i,j)=1]=\sum_{d|i,d|j} \mu(d)$ -

$\sum_{i=1}^{n}\sum_{i=1}^{m}[\gcd(i,j)=k]=$

$\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} \mu(d)\lfloor\frac{n}{d k}\rfloor\lfloor\frac{m}{d k}\rfloor$ [【例题】](https://www.luogu.com.cn/problem/P3455) -

$\sum_{i=1}^{n}\sum_{i=1}^{m}[\gcd(i,j)\in \{Prime\}]=$

$\sum_{d=1}^{n}\left(\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\sum_{p | d\ \&\ p\in\{Prime\}} \mu(\frac{d}{p})\right)$ [【例题】](https://www.luogu.com.cn/problem/P2257) -

$\sum_{i=1}^{n} \sum_{j=1}^{m} \operatorname{lcm}(i,j)=$

$\sum_{d=1}^{n} d\left(\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor} x^{2} \mu(x) \sum_{i=1}^{\lfloor\frac{n}{dx}\rfloor} i\sum_{i=1}^{\lfloor\frac{m}{dx}\rfloor} j \right)$ [【例题】](https://www.luogu.com.cn/problem/P1829) ##### **(2).【除数函数】** -

$\sigma_{k}=\sum_{d|n}d^{k}$ （即

$\sigma_{k}=\operatorname{id}_{k}\ast1$ ） -

$\sigma_0(xy)=\sum_{i|x} \sum_{j|y}[\operatorname{gcd}(i,j)=1]$ （其中

$\sigma_0(x)$ 表示

$x$ 的约数个数） -

$\sum_{i=1}^{n}\sigma_0(i)=$

$\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor$ [【例题】](https://www.luogu.com.cn/problem/P3935) -

$\sum_{i=1}^{n} \sum_{j=1}^{m} \sigma_0(ij)=$

$\sum_{k=1}^{n}\mu(k)\left(\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\lfloor{\frac{n}{ik}}\rfloor\right)\left(\sum_{i=1}^{\lfloor\frac{m}{k}\rfloor}\lfloor\frac{m}{i k}\rfloor\right)$ [【例题】](https://www.luogu.com.cn/problem/P3327) -

$\sigma_{1}(xy)=\sum_{i\mid x}\sum_{j\mid y} \frac{iy}{j}[\gcd(i,j)=1]$ （其中

$\sigma_0(x)$ 表示

$x$ 的约数和） -

$\sum_{i=1}^{n}\sum_{j=1}^{n}\sigma_1(ij)=$

$\sum_{d=1}^{n}\mu(d)d \left(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sigma_1(i)\right)^{2}$ [【例题】](http://www.51nod.com/Challenge/Problem.html#problemId=1220) -

$\sum_{i=1}^{n}\sum_{j=1}^{m} \sigma_1(\gcd(i,j))=$

$\sum_{d=1}^{n}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\left(\sum_{i|d}\mu(\frac{d}{i}) \sigma_1(i)\right)$ [【例题】](https://www.luogu.com.cn/problem/P3312) ##### **(3).【莫比乌斯函数】** -

$\sum_{k=1}^{n}\mu^{2}(k)=\sum_{d=1}^{\sqrt{n}}\mu(d)\lfloor \frac{n}{d^{2}}\rfloor$ [【例题】](https://www.luogu.com.cn/problem/P4318) -

$\sum_{i=1}^{n}\mu^2(i)\sqrt{\frac{n}{i}}=n$ [【证明】](https://www.cnblogs.com/Xing-Ling/p/12760629.html) ### **3.【二项式反演】** #### **【基本性质、定理】** -

$f(n)=\sum_{i=0}^{n}C_{n}^{i}g(i) \Longleftrightarrow$

$g(n)=\sum_{i=0}^{n}(-1)^{n-i}C_{n}^{i}f(i)$ -

$f(n)=\sum_{i=0}^{n}(-1)^{i}C_{n}^{i}g(i)\Longleftrightarrow$

$g(n)=\sum_{i=0}^{n}(-1)^{i}C_{n}^{i}f(i)$ -

$f(n)=\sum_{i=n}^{?}C_{i}^{n}g(i) \Longleftrightarrow$

$g(n)=\sum_{i=n}^{?}(-1)^{i-n}C_{i}^{n}f(i)$ [【例题】](https://www.luogu.com.cn/problem/P4491) [【例题】](https://www.luogu.com.cn/problem/P6478) -

$f(n)=\sum_{i=n}^{?}(-1)^{i}C_{i}^{n}g(i)\Longleftrightarrow$

$g(n)=\sum_{i=n}^{?}(-1)^{i}C_{i}^{n}f(i)$ -

$f(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}C_{n}^{i}C_{m}^{j}g(i,j) \Longleftrightarrow$

$g(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}(-1)^{n+m-i-j}C_{n}^{i}C_{m}^{j}f(i,j)$ -

$f(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}(-1)^{i+j}C_{n}^{i}C_{m}^{j}g(i,j) \Longleftrightarrow$

$g(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}(-1)^{i+j}C_{n}^{i}C_{m}^{j}f(i,j)$ -

$f(n,m)=\sum\limits_{i=n}^{?}\sum\limits_{j=m}^{?}C_{i}^{n}C_{j}^{m}g(i,j) \Longleftrightarrow$

$g(n,m)=\sum\limits_{i=n}^{?}\sum\limits_{j=m}^{?}(-1)^{i+j-n-m}C_{i}^{n}C_{j}^{m}f(i,j)$ [【例题】](https://www.luogu.com.cn/problem/CF1228E) [【例题】](https://www.luogu.com.cn/problem/CF997C) -

$f(n,m)=\sum\limits_{i=n}^{?}\sum\limits_{j=m}^{?}(-1)^{i+j}C_{i}^{n}C_{j}^{m}g(i,j) \Longleftrightarrow$

$g(n,m)=\sum\limits_{i=n}^{?}\sum\limits_{j=m}^{?}(-1)^{i+j}C_{i}^{n}C_{j}^{m}f(i,j)$ ### **4.【斯特林反演】** #### **【基本性质、定理】** -

$f(n)=\sum_{i=0}^{n} S_{n}^{i} g(i) \Longleftrightarrow$

$g(n)=\sum_{i=0}^{n}(-1)^{n-i} s_{n}^{i} g(i)$ -

$f(n)=\sum_{i=0}^{n}s_{n}^{i}g(i)\Longleftrightarrow$

$g(n)=\sum_{i=0}^{n}(-1)^{n-i}S_{n}^{i}f(i)$ -

$f(n)=\sum_{i=n}^{?} S_{i}^{n} g(i) \Longleftrightarrow$

$g(n)=\sum_{i=n}^{?}(-1)^{i-n} s_{i}^{n} g(i)$ -

$f(n)=\sum_{i=n}^{?}s_{i}^{n}g(i)\Longleftrightarrow$

$g(n)=\sum_{i=n}^{?}(-1)^{i-n}S_{i}^{n}f(i)$ ### **5.【单位根反演】** #### **【基本性质、定理】** -

$[n|k]=\frac{\sum_{i=0}^{n-1}w_{n}^{ik}}{n}$ - $[a=b]=\frac{\sum_{i=0}^{n-1} w_{n}^{a i} w_{n}^{-i b}}{n}(a,b