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

数论相关

常见的积性函数

单位函数

欧拉函数

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

莫比乌斯函数

正因子数

因子函数

易知
一般记作

常值函数

幂函数

特别的,常记作

狄利克雷卷积

对于两个数论函数

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

性质

1.对于任意的数论函数f有
$$

2.$$

3.$$

4.$$

莫比乌斯反演

如果

那么有

莫比乌斯反演常用卷积:

约数个数定理

证明:其实很显然,只要枚举每种质因子的出现在约数中的个数就能得到所有的约数。对于在里出现了次的质因子,在约数里面有中选择,即选个。

拉格朗日插值

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

中国剩余定理

对于一个同余方程组。如果满足两两互质。

那么就有

其中

组合相关

二项式定理

广义二项式定理:

多项式相关

由1式求导得

由上式求导得

其他小知识点