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

全部评论

推荐最新楼层

不愿透露姓名的神秘牛友

07-11 11:21

好喜欢hr姐姐啊啊啊

被夸真的超级开心，好可爱的姐姐

码农索隆：老色批们不用脑补了，我把金智妮的图找来了

查看图片

点赞评论收藏

分享

07-09 22:05

门头沟学院游戏后端

26届双非小厂实习一个月被辞退

鼠鼠是一名26届双非的大三生，今天下午在看文档是被人事叫到办公室谈离职。原因是带鼠鼠的那位（专业称呼应该是叫mentor吧）觉得我主动性和积极性不足，以及加班时间不够。 先说一下公司和mentor的情况，公司是一家软件和硬件都做的小公司，10年了人数稳定在50~60人。其他年份不清楚招收情况，反正今年光我之后来的就有五六个，公司是大小周，上班时间是上午9：00到下午6点，但是，要加班。硬件部门要加到8点，软件部门要加到9点，面试的时候只是说可能加班有点多，到我入职就成了硬性加班了，加班费从6点加到9点有20块。我的mentor是个大忙人，看样子应该身兼好几个项目，所以经常见不到他，早上到公司一...

点赞评论收藏

分享

06-10 11:37

已编辑

陕西理工大学 Java

有点抽象，面了7分钟，然后就过了。真点击即送。问了下体重啥的，然后让我用日语介绍了下，讲了下项目，就没了。？？？

阿14：在东软摸鱼算不算抗日

东软集团开奖3人在聊

点赞评论收藏

分享

07-09 15:03

广州软件学院前端工程师

面试官问我：你简历上的项目真是你做的吗？😱我这么回答…

UU们！今天想和你们聊一个很多人求职时都会偷偷问的问题👇 —— 简历里加点水分，算不算造假？ 作为一个从实习生一路卷到前端主力的老阿姨👩💻 （是的，我也有过“美化”简历的经历🤫） 我想坦白地说一句： 👉 几乎每个求职者，都在简历上做过一点“艺术加工”。 但重点来了👇 什么程度叫“润色”，什么程度叫“翻车”？ 这中间的差别，真的能决定你能不能拿到offer，还是直接被pass！ 🤔【1】什么是“有水分”？我和HR聊过才知道 所谓的“简历水分”，其实分两种： ✅ 良性“润色”（加分项） 比如：  把实习中参与的小项目整合成“模块开发经验” 把自己负责的部分写得更专业一些 用行业术语描...

简历当中有水分算不算造假...

点赞评论收藏

分享

评论

1

收藏

全站热榜

更多

创作者周榜

更多

正在热议

更多

# 技术岗笔试题求解 #

77597次浏览 1005人参与

# 拼多多求职进展汇总 #

642348次浏览 4983人参与

# 工作一周年分享 #

30698次浏览 179人参与

# 如果公司给你放一天假，你会怎么度过？ #

16250次浏览 122人参与

# 作业帮求职进展汇总 #

55758次浏览 370人参与

# 华子oc时间线 #

1236419次浏览 6473人参与

# OPPO求职进展汇总 #

662180次浏览 5032人参与

# 总结:哪家公司面试体验感最差 #

60476次浏览 273人参与

# 职场上哪些事情令人讨厌 #

18719次浏览 91人参与

# 三一重工求职进展汇总 #

14313次浏览 65人参与

# 去年你投递实习了吗？ #

21995次浏览 329人参与

# 这些公司卡简历很严格 #

41290次浏览 204人参与

# 扒一扒那些奇葩实习经历 #

66306次浏览 913人参与

# 经纬恒润求职进展汇总 #

121666次浏览 1032人参与

# 提前批过来人的忠告 #

113864次浏览 1194人参与

# 说说你知道的学历厂 #

58392次浏览 351人参与

# 秋招最大的收获是什么？ #

36871次浏览 311人参与

# 找工作时的取与舍 #

80012次浏览 566人参与

# 你认为小厂实习有用吗？ #

29317次浏览 341人参与

# 哪一瞬间觉得自己长大了 #

13914次浏览 327人参与

牛客网
牛客网在线编程
牛客网题解
牛客企业服务