2020-02-20 20:19 已编辑字节跳动_后端开发工程师

关注

数学-Dirichlet卷积

在oi-wiki上学了不少，做一点笔记

积性函数

定义

若对于任意的 $gcd(x,y)==1$ 总有 $f(xy)=f(x)f(y)$ 则函数 $f$ 称为积性函数
若对任意的 $x,y$ ，都有 $f(xy)=f(x)f(y)$ 则函数 $f$ 称为完全积性函数

性质

若 $f(x)$ 和 $g(x)$ 都是积性函数，则 $h(x)=f(x^p)\\ h(x)=f^p(x)\\ h(x)=f(x)g(x)\\ h(x)=\sum_{d|x}f(d)g(\frac{x}{d})$
都是积性函数

举例

单位函数 $\epsilon(x)= \left.\begin{cases}1\quad x=1\\0\quad x\ne1\end{cases}\right.$
恒等函数 $ID(x)=x$ ——x是几就是几
常数函数 $1(x)=1$ ——x是几都是1
欧拉函数 $\phi(x)$ —— $\lt x$ 且与 $x$ 互质的数的个数
莫比乌斯函数 $\mu(x)=\left.\begin{cases}1\quad x=1\\0\quad x的因子中有平方数\\(-1)^k\quad k是x的质因子个数\end{cases}\right.$

Dirichlet卷积

定义

对于两个数论函数 $f(n),g(n)$ 他们的迪利克雷卷积是 $(f*g)(n)=\sum_{d|n}f(d)*g(\frac{n}{d})$ 也就是也就是对于 $i*j==n$ 的整数 $i,j$ 的函数值乘在一起再求和

性质

dirichlet卷积满足结合律和交换律
单位函数 $\epsilon(x)$ 是dirichlet卷积的单位元，任何函数卷上 $\epsilon(x)$ 都是它本身

需要记住的结论

$\epsilon(x)=\sum_{d|n}\mu(d)*1(\frac nd)$
$ID(x)=\sum_{d|n}\phi(d)*1(\frac nd)$
$\phi(x)=\sum_{d|n}ID(d)*\mu(\frac nd)=\sum_{d|n}d\mu(\frac nd)$

一些显然的结论

$x的因子个数=\sum_{d|n}1(d)*1(\frac nd)=\sum_{d|n}1$
$x的因子和=\sum_{d|n}ID(d)*1(\frac nd)=\sum_{d|n}d$

莫比乌斯反演

若对于两个数论函数 $f,g$ 有 $f(n)=\sum_{d|n}g(d)\\$ 则 $g(n)=\sum_{d|n}\mu(d)f(\frac nd)\\$

证明

原式等于： $f(n)=(g*1)(n)\\$
两边同时卷积 $\mu(n)$
$(f\mu)(n)=(g*1*\mu)(n)\\$
因为 $(\mu*1)(n)=\epsilon(n)\\$
所以

$(f\mu)(n)=(g*\epsilon)(n)=g(n)\\$
即 $g(n)=\sum_{d|n}\mu(d)f(\frac nd)\\$

全部评论

推荐最新楼层

07-01 15:41

门头沟学院机械工程师

哦莫，现在找个工作都要付费了吗

点赞评论收藏

分享

不愿透露姓名的神秘牛友

07-01 14:55

这样的实习，我还有必要坚持下去吗？

先说一下背景：我现在是26届大三，进了一个小公司，一共就一个老板两个员工现在今天试岗第二天（试岗没有工资），昨天一来看到我本人，就说一看我就娇滴滴，抗压能力差…什么都没有干已经被攻击了……昨天下午教我工作，我一问问题他说一遍我做就行了，又把我说了一顿（因为可能她的工作很多，觉得我烦？）然后今天领导来了检查我的工作，说我做的都不对，只知道坐在那不知道问，然后站我旁边说了我快五十分钟，顺便攻击我学校不好（我是二本）所以能力差我不知道现在是应该跑路还是接着在干，朋友都让让我跑吧，但家里又说让我坚持而且就算是后面正式实习也就一天80块钱，甚至我面试问了句是单休还是双休，这老板都要说我问这个是不是单休就...

Twilight_m...：这人还说佬抗压能力弱，我觉得佬抗压能力太强了，要这情况我可能都干不到第二天

实习，不懂就问

点赞评论收藏

分享

05-17 11:07

桂林航天工业学院运营

感觉自己素质越来越低了

求offer的大角牛：不吃香菜

点赞评论收藏

分享

06-03 11:31

四川轻化工大学 Java

大三找实习，大家可以给点意见吗，这个简历有什么问题

不想上班的芝士很想居...：smm是什么技术

实习，投递多份简历没人回...

点赞评论收藏

分享

不愿透露姓名的神秘牛友

07-04 15:36

左脚出学校右脚进腾讯

携手女友进腾讯啦~不过可惜的是我俩不是一个部门！base地也不一样，但是可以系统里看到我俩，这下好了到哪里都能聊天了

腾讯开奖367人在聊

点赞评论收藏

分享

评论

点赞

收藏

全站热榜

更多

创作者周榜

更多

正在热议

更多

# 大家每天通勤多久？ #

45955次浏览 346人参与

# 银行笔面经互助 #

134340次浏览 1169人参与

# 现代汽车前瞻技术研发急速编程挑战赛 #

33779次浏览 259人参与

# 上班到公司第一件事做什么？ #

58657次浏览 500人参与

# 设计人如何选offer #

119363次浏览 741人参与

# CVTE求职进展汇总 #

16452次浏览 292人参与

# 上班苦还是上学苦呢？ #

229738次浏览 1357人参与

# 非技术投递记录 #

604591次浏览 6402人参与

# 90后北漂现状 #

24924次浏览 201人参与

# 百度工作体验 #

227053次浏览 1997人参与

# 机械人与华为的爱恨情仇 #

117921次浏览 951人参与

# 金融财会交流会 #

110623次浏览 380人参与

# 工作中，努力重要还是选择重要？ #

137299次浏览 1683人参与

# 发工资后，你做的第一件事是什么 #

68801次浏览 232人参与

# 机械人，你的秋招第一份简历被谁挂了 #

141770次浏览 1982人参与

# Offer比较，你最看重什么？ #

187046次浏览 1288人参与

# 工作中哪个瞬间让你想离职 #

26485次浏览 179人参与

# 你觉得实习能学到东西吗 #

41109次浏览 783人参与

# 秋招什么时候开投比较合适？ #

29223次浏览 354人参与

# 联想求职进展汇总 #

271101次浏览 2053人参与

# 机械人集合！你是什么工程师？ #

16432次浏览 89人参与

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