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)$

全部评论

推荐最新楼层

04-02 18:17

虾皮信息_后端开发工程师(准入职员工)

虾皮内推-虾皮内推码

先分享一下在shopee工作是什么样的心情✌🏻 我对公司的第一印象就是 这公司也太大了吧 员工也非常多！加上设备很齐全 尤其是pantry 太适合我这种吃货了!🤣 ✨工作量会比较多 在Shopee的活动期例如双十一，双十二，周末也得加班哦 ✨工作环境棒棒哒 同事们很友善也很愿意帮助新人的我 目前满enjoyable的 ✨公司地点方便 Shopee公司处在于midvalley 的对面，交通都很方便呢！享用午餐地点选择也多😋 ✨穿着自由 通常我都是穿搭轻松casual上班去😆你要casual，formal 或 trendy都可以！非常的自由 ✨工资方面 相信大家都对这个比较好奇 个人觉得S...

虾皮信息公司氛围 202人发布

点赞评论收藏

分享

04-01 19:48

三七互娱_游戏开发_系统开发(准入职员工)

三七互娱内推三七互娱内推

办公环境：三七互娱的办公环境现代化且舒适，为员工提供了良好的工作空间。公司内部设施齐全，可能包括休息区、咖啡吧等，有助于员工在紧张的工作之余放松身心，同时三七互娱给所有符合条件的员工提供最高50万住房免息贷款，累计发放近5000万元，后续发放人数也会不断增加。企业文化：三七互娱注重年轻化和活力，公司文化较为开放和包容。同事和领导多为年轻人，相处模式较为轻松，有利于实习生快速融入团队并建立良好的工作关系。工作内容：在三七互娱可能会接触到游戏行业的多个环节，如游戏运营、市场推广、产品研发等。具体工作内容会根据实习岗位和部门的不同而有所差异，但都会让实习生有机会深入了解游戏行业的运作机制。学习机会：...

三七互娱公司福利 324人发布

点赞评论收藏

分享

02-23 12:32

已编辑

门头沟学院嵌入式工程师

二战失败，简历被挂求建议

King987：学历没有问题，然后既然有实习经历的话，把这个放在上面多写一点，哪怕你自己包装一下，只要能圆回来就行，既然有实习经历的话，肯定主要看实习经历之类的。然后也会主要问这里多准备准备

点赞评论收藏

分享

02-26 16:52

门头沟学院 Java

怎么会这样，还以为要我简历来了

Lunarloop：董事长亲自到ssob来要IM项目的技术方案来了

点赞评论收藏

分享

04-02 14:11

腾讯_前端(实习员工)

抑郁过后，我更加热爱这个世界

序 朋友们，好久不见。 笔者在过去消失的五个月里被困在情绪牢笼中过的相当煎熬，一度丢失自己，觉得整个世界都是昏暗的。 庆幸的是靠着自己纯硬扛也是走出来了。表达欲再度回归，所以真的很开心还有机会能在再和大家见面。 破碎秋招 抑郁情绪的引爆点必然是秋招期间遭受的打击了，从去年九月份腾讯转正被告知失败之后就开始疯狂投递简历，每天都在经历：简历挂、一面挂、二面挂、三面挂、HR面挂，每天睁开眼就被无所适从的挫败感包围。 秋招的特点是即便流程走到最后一步也不一定会 offer，因为还需要进入大池子进行横向对比，俗称泡池子，而这一泡我的大多数面试流程到后面就没了后文，这一度让我感觉非常绝望。我深知自己学历并...

SoNiC_X：我已经工作快2年了，当时高考没考好没去到想去的学校，觉得天要塌了；校招找不到工作，觉得天要塌了；现在工作觉得看不到未来，觉得天要塌了；最近最大的感悟就是：天会一直塌，但是生活也会一直继续下去，还是要调整好自己的心态，不要因为一时的困难把自己困住，要记住完蛋的日子永远在后头

当你面对裁员会如何？你的秋招简历被谁挂了？

点赞评论收藏

分享

评论

1

收藏

全站热榜

更多

创作者周榜

更多

正在热议

更多

2357340次浏览 27441人参与

# 如果没找到工作，考公是你的退路吗 #

16954次浏览 195人参与

# 牛友故事会 #

516116次浏览 11756人参与

# 多益网络求职进展汇总 #

7596次浏览 47人参与

# 不考虑薪资和职业，你最想做什么工作呢？ #

68057次浏览 586人参与

# 你上一次加班是什么时候？ #

43598次浏览 311人参与

# 实习中的菜狗时刻 #

327388次浏览 3096人参与

# 关于春招你都做了哪些准备？ #

79540次浏览 528人参与

# 产品2023笔面经 #

47007次浏览 423人参与

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

113589次浏览 629人参与

# 新凯来求职进展汇总 #

15577次浏览 66人参与

# 蔚来求职进展汇总 #

85199次浏览 746人参与

# 找工作有哪些冷知识 #

21049次浏览 247人参与

# 秋招被确诊为…… #

152064次浏览 697人参与

# 金蝶求职进展汇总 #

41531次浏览 234人参与

# 百度秋招提前批进度 #

99597次浏览 1111人参与

# 机械人的offer怎么选 #

128190次浏览 736人参与

# 小厂实习有必要去吗 #

39189次浏览 249人参与

# 谈薪时HR压价该怎么应对 #

190202次浏览 3066人参与

# 京东工作体验 #

11813次浏览 84人参与

牛客网
牛客企业服务