这篇文章主要是整理一些定理,方便后面复习。没有证明(学OI要什么证明)。
数论相关
常见的积性函数
单位函数
欧拉函数
表示小于等于n的数字中与n互质的数字个数。
莫比乌斯函数
正因子数
因子函数
易知
一般记作
常值函数
幂函数
特别的,常记作
狄利克雷卷积
对于两个数论函数,
其中*为狄利克雷卷积的运算符号。如果f和g为积性函数,那么也为积性函数。
性质
1.对于任意的数论函数f有
$$
2.$$
3.$$
4.$$
莫比乌斯反演
如果
那么有
莫比乌斯反演常用卷积:
约数个数定理
证明:其实很显然,只要枚举每种质因子的出现在约数中的个数就能得到所有的约数。对于在里出现了次的质因子,在约数里面有中选择,即选个。
拉格朗日插值
拉格朗日插值可以在给定n个点的情况下,在复杂度内找到原多项式在位置的取值。
中国剩余定理
对于一个同余方程组。如果满足两两互质。
那么就有。
其中
组合相关
二项式定理
广义二项式定理:
多项式相关
由1式求导得
由上式求导得