wxyww

精品数学知识点整理

精品

未归档(12) 题解(65)

/ 注册

数学知识点整理

512 浏览 0 回复 2020-05-22

wxyww

+关注

这篇文章主要是整理一些定理，方便后面复习。没有证明~~(学OI要什么证明)~~。

数论相关

常见的积性函数

单位函数

$\epsilon(n)=[n=1]$

欧拉函数

$\varphi(n)=n\sum(1-\frac{1}{p_i})$

表示小于等于n的数字中与n互质的数字个数。

莫比乌斯函数

$\mu(x)=\begin{cases}1 &(x=1)\\ (-1)^k & x=p_1p_2...p_k\\ 0 & else\end{cases}$

正因子数

$d(n)=\sum\limits_{i|n}1$

因子函数

$\sigma_k(n)=\sum\limits_{d|n}d^k$

易知 $\sigma_0(n)=d(n)$
$\sigma_1(n)$ 一般记作 $\sigma(n)$

常值函数

$1(n)=1$

幂函数

$Id_k(n)=n^k$

特别的， $Id_1(n)$ 常记作 $Id(n)$

狄利克雷卷积

对于两个数论函数 $f$ ， $g$

$f*g(n)=\sum\limits_{d|n}f(d)g(\frac{n}{d})$

其中*为狄利克雷卷积的运算符号。如果f和g为积性函数，那么 $f*g$ 也为积性函数。

性质

1.对于任意的数论函数f有
$ $f*\epsilon=f$ $

2.$ $Id = 1*\varphi$ $

3.$ $\epsilon=1*\mu$ $

4.$ $\sigma_k=1*Id_k$ $

莫比乌斯反演

如果 $g=f*1$

那么有 $f=f*\epsilon=f*1*\mu=g*\mu$

莫比乌斯反演常用卷积： $\mu*1=\epsilon,Id=1*\varphi$

约数个数定理

$n=\prod p_i^{k_i}\Rightarrow\sigma(n) = \sum\limits_{d|n}1=\prod (k_i+1)$

证明：其实很显然，只要枚举每种质因子的出现在约数中的个数就能得到所有的约数。对于在 $n$ 里出现了 $k$ 次的质因子，在约数里面有 $k+1$ 中选择，即选 $0,1,2...k$ 个。

拉格朗日插值

拉格朗日插值可以在给定n个点的情况下，在 $O(n^2)$ 复杂度内找到原多项式在 $k$ 位置的取值。

$f(k)=\sum\limits_{i=0}^n y_i\prod\limits_{j\neq i}\frac{k-x_j}{x_i-x_j}$

中国剩余定理

对于一个同余方程组 $\begin{cases}x \equiv a_1(mod\ m_1)\\x\equiv a_2(mod\ m_2)\\ \cdots\\ x\equiv a_n(mod\ m_n)\end{cases}$ 。如果满足 $m_1,m_2...m_n$ 两两互质。

那么就有 $x\equiv\sum\limits_{i=1}^na_i\frac{M}{a_i}(\frac{M}{a_i})^{-1}_{m_i}(mod\ M)$ 。

其中 $M=\prod\limits_{i=1}^na_i$

组合相关

二项式定理

$(a+b)^n=\sum\limits_{i=0}^nC_n^ia^ib^{n-i}$

广义二项式定理:

$\frac{1}{(1-x)^n}=\sum\limits_{k>0}C_{n+k-1}^k x^k$

多项式相关

$\frac{1}{1-x}=1+x+x^2+x^3+...$ $\frac{1}{1-x^2}=1+x^2+x^4+x^6+...$ $\frac{1}{1-x^k}=1+x^k+x^{2k}+x^{3k}+...$ $\frac{1}{1-kx}=1+kx+k^2x^2+k^3x^3+...$ $\frac{2}{1-x}=2+2x+2x^2+2x^3+...$ $\frac{x^k}{1-x}=x^{k}+x^{k + 1} + x^{k+2}+...$

由1式求导得 $\frac{1}{(1-x)^2}=1+2x+3x^2+4x^3+...$

由上式求导得 $\frac{2}{(1-x)^3}=2+6x+12x^2+20x^3+...$

其他小知识点

$\lfloor\frac{\lfloor\frac{n}{i}\rfloor}{x}\rfloor=\lfloor\frac{n}{ix}\rfloor$

$\sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor=\sum\limits_{i=1}^nd(i)$

数学

举报

收藏

赞 1

评论加载中...