数学知识点

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

数论相关

常见的积性函数

单位函数

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

欧拉函数

[varphi(n)=nsum(1-frac{1}{p_i}) ]

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

莫比乌斯函数

[mu(x)=egin{cases}1 &(x=1)\ (-1)^k & x=p_1p_2...p_k\ 0 & elseend{cases}]

正因子数

[d(n)=sumlimits_{i|n}1 ]

因子函数

[sigma_k(n)=sumlimits_{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)=sumlimits_{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}Rightarrowsigma(n) = sumlimits_{d|n}1=prod (k_i+1))

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

拉格朗日插值

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

[f(k)=sumlimits_{i=0}^n y_iprodlimits_{j eq i}frac{k-x_j}{x_i-x_j} ]

中国剩余定理

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

那么就有(xequivsumlimits_{i=1}^na_ifrac{M}{a_i}(frac{M}{a_i})^{-1}_{m_i}(mod M))。

其中(M=prodlimits_{i=1}^na_i)

组合相关

二项式定理

[(a+b)^n=sumlimits_{i=0}^nC_n^ia^ib^{n-i} ]

广义二项式定理:

[frac{1}{(1-x)^n}=sumlimits_{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+...)

其他小知识点

(lfloorfrac{lfloorfrac{n}{i} floor}{x} floor=lfloorfrac{n}{ix} floor)

(sumlimits_{i=1}^nlfloorfrac{n}{i} floor=sumlimits_{i=1}^nd(i))