2020-05-22 18:08 山东大学 Java

关注

数学知识点整理

这篇文章主要是整理一些定理，方便后面复习。没有证明~~(学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)$

全部评论

推荐最新楼层

11-20 10:41

重庆邮电大学数据库工程师

佬们，目前就这三个offer，优先级怎么排呀

秋招的第一个offer，大家都拿到了吗

点赞评论收藏

分享

昨天 12:02

西南大学 HTML5

国企也可能是草台班子，甚至更水

其实，很多应届生都是普通本科，国企的考试对我们这些人相对宽容，完全看个人的学习能力，公平性还是很高的。现在正是备考的好时机！我发现校招是最适合我们的方式，国企直接进校园招聘，保障性更强。网申时，记得注册账号，简历要简洁大方，关键词要突出。备考时，行测和申论可以用粉笔的题库练习，专业知识就复习大学课本，企业文化了解一下就好，难度不大。大家一起加油吧！

投递粉笔网等公司10个岗位 > 牛客创作赏金赛

点赞评论收藏

分享

10-16 16:19

第一拖拉机制造厂拖拉机学院 Java

秋招第一个oc

牛客771574427号：恭喜你，华杰

点赞评论收藏

分享

10-15 16:27

门头沟学院 C++

感觉被侮辱了

LeoMoon：建议问一下是不是你给他付钱😅😅

点赞评论收藏

分享

11-22 18:29

北京理工大学算法工程师

预计下个星期就能开奖吧，哪位老哥来给个准信

华孝子爱信等：对接人上周说的是这周

点赞评论收藏

分享

1 收藏评论

全站热榜

正在热议

# 25届秋招总结 #

263913次浏览 2185人参与

# 0offer是寒冬太冷还是我太菜 #

887429次浏览 7909人参与

# 北方华创开奖 #

23664次浏览 260人参与

# 地方国企笔面经互助 #

2846次浏览 7人参与

# 学历or实习经历，哪个更重要 #

43437次浏览 328人参与

# 选完offer后，你后悔学本专业吗 #

13258次浏览 94人参与

# 查收我的offer竞争力报告 #

19520次浏览 255人参与

# 应届生被毁约被毁意向了怎么办 #

28202次浏览 243人参与

# 你最想要的公司福利是？ #

41868次浏览 146人参与

# 如何一边实习一边秋招 #

987374次浏览 12609人参与

# 一觉醒来，我觉醒了超级打工人系统 #

3305次浏览 36人参与

# 嵌入式转岗的难度怎么样 #

11199次浏览 251人参与

# 你最希望上岸的公司是？ #

76541次浏览 469人参与

# 如何写一份好简历 #

605037次浏览 8509人参与

# 面试体验感最好的是哪家？ #

83650次浏览 818人参与

# 机械应届生薪资要多少才合适？ #

12542次浏览 61人参与

# 牛客十周岁生日快乐 #

48746次浏览 759人参与

# 你认为第一份工作重要吗 #

5447次浏览 49人参与

# 985本硕1个中小厂offer，摆烂or继续努力 #

79942次浏览 589人参与

# 秋招OC许愿 #

228208次浏览 1880人参与

# 来聊聊机械薪资天花板是哪家 #

65735次浏览 445人参与

牛客网
牛客企业服务