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-19 16:15

已编辑

中南大学 Java

人生充满了遗憾

在深圳实习完忙着秋招的时候有朋友叫我一起去外面玩，说以后可能很久都没机会来深圳了，不去玩会留下遗憾，我还是三方五次拒绝了，我当时的想法是：人生充满了遗憾，多一个少一个对我来说根本无所谓，我的评价是也就这b样了。秋招结束，春招启动！

求offer的社畜很想吃卤蛋：篮子对快手是不满意吗

牛客创作赏金赛 25届秋招总结

点赞评论收藏

分享

11-17 18:39

网易有道_Java开发工程师(准入职员工)

二本学院非科班天崩开局，如何逆天改命拿下大厂后端

天崩开局，如何破局自救2021 年高考结束，我当时的第一志愿是计算机科学与技术专业，但是我被录取到了河南工程学院的高分子材料与工程专业。我去咨询计算机相关行业的从业者，以及多方面网络搜集相关信息之后得到了一个很现实的消息——二本学院本+非科班双重debuff对于我想从事的计算机行业来说，就是死局。于是我在大一期间的目标其实非常明确：自学计算机转专业到计算机科学与技术所以目标有了之后就很简单了，我在暑假开学前就开始学习Python，然后快开学的时候就开始在校内打听转专业相关信息，并且联系到了以前转专业成功的学长。期间还认识了一位打ACM竞赛的优秀学长（也是我之后参加ACM的队友），在他的推荐下，...

许愿后端：很喜欢的一句话，少年一定要所失，才能有所悟。送给你，加油

牛客创作赏金赛

点赞评论收藏

分享

09-27 09:26

湖南女子学院运营

求大佬改简历

普通二本真的已经迷茫了，简历修改了很多版，但是还是感觉不太好，希望大家给给建议

荒野星伊：是真的好看，kao（语气词）！

点赞评论收藏

分享

10-30 17:07

University of California Riverside UE4

某些HR能不能有点职业素养

朋友圈挂人骂人巨婴😅😅

我已成为0offer的糕手：别惯着，胆子都是练出来的，这里认怂了，那以后被裁应届被拖工资还敢抗争？

点赞评论收藏

分享

11-22 18:10

四川大学其他机械职位

班味就这么水灵灵的来了

最近和朋友聊天，她说了句让我震惊的话:"我发现我连周末点外卖都开始'最优解'了，一定要赶在高峰期前下单，不然就觉得自己亏了。"这不就是典型的"班味入侵"吗?工作思维已经渗透到生活的方方面面。

小型域名服务器：啊？我一直都这样啊？我还以为是我爱贪小便宜呢？

每次去实验室都得接一杯免费的开水回去，出门都得规划一下最短路径，在宿舍就吃南边的食堂，在实验室就吃北边的食堂，快递只有顺路的时候才取。

点赞评论收藏

分享

1 收藏评论

全站热榜

正在热议

# 25届秋招总结 #

264543次浏览 2194人参与

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

887643次浏览 7910人参与

# 北方华创开奖 #

23696次浏览 260人参与

# 地方国企笔面经互助 #

2849次浏览 7人参与

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

43492次浏览 329人参与

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

13373次浏览 94人参与

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

19627次浏览 256人参与

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

28249次浏览 243人参与

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

41919次浏览 146人参与

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

987471次浏览 12609人参与

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

3325次浏览 36人参与

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

11210次浏览 251人参与

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

76595次浏览 469人参与

# 如何写一份好简历 #

605139次浏览 8511人参与

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

83678次浏览 818人参与

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

12547次浏览 61人参与

# 牛客十周岁生日快乐 #

48786次浏览 759人参与

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

5458次浏览 49人参与

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

79965次浏览 589人参与

# 秋招OC许愿 #

228280次浏览 1881人参与

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

65797次浏览 445人参与

牛客网
牛客企业服务