2021-06-19 19:31 已编辑广州大学 C++

关注

题解 | #Calculation#

Calculation

https://ac.nowcoder.com/acm/contest/17796/A

首先考虑改变枚举顺序消去 $[i\mid j\space and\space j\mid k]$ ：

$\begin{aligned} &\Rightarrow\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{k=1}^{\lfloor\frac{n}{j}\rfloor}\lambda(i)\lambda(j)[i\mid j] \\&=\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}\sum\limits_{k=1}^{\lfloor\frac{n}{ij}\rfloor}\lambda(i)\lambda(ij) \\&=\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}\lfloor\frac{n}{ij}\rfloor\lambda(i)\lambda(ij) \end{aligned}$

考虑刘维尔函数的定义，显然这个函数为完全积性函数且对于一个平方数 $x^2$ ，一定有 $\lambda(x^2)=1$ ，那么：

$\begin{aligned} &\Rightarrow\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}\lfloor\frac{n}{ij}\rfloor\lambda(i^2j) \\&=\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}\lfloor\frac{n}{ij}\rfloor\lambda(j) \\&=\sum\limits_{T=1}^n\lfloor\frac{n}{T}\rfloor\sum\limits_{d\mid T}\lambda(d) \end{aligned}$

第三步是枚举 $T=ij$ 时得出来的转变。
现在只需要求解后一部分的 $\sum\limits_{d\mid T}\lambda(d)$ 。
考虑 $\lambda(n)$ 的贝尔级数，不懂贝尔级数的读者可以到这篇文章进行学习。

$\lambda_p(x)=1-x+x^2-x^3+\cdots \\x\lambda_p(x)=x-x^2+x^3-x^4+\cdots \\(1+x)\lambda_p(x)=1 \\\lambda_p(x)=\frac{1}{1+x}$

这里的 $\sum\limits_{d\mid T}\lambda(d)$ 相当于：

$(\lambda*1)(x)\Rightarrow\lambda_p(x)1_p(x)=\frac{1}{1+x}\times\frac{1}{1-x}=\frac{1}{1-x^2}$

逆推一下这个式子可以得到：

$\\f_p(x)=\frac{1}{1-x^2} \\f_p(x)=1+x^2f_p(x) \\f_p(x)=1+0+x^2+0+x^4+\cdots$

所以函数 $f(x)$ 的意义是什么？由于两个积性函数的狄利克雷卷积仍是积性函数，那么当且仅当一个数的所有质因数的幂次可以被 $2$ 整除时， $f(x)=1$ ，否则 $f(x)=0$ 。说明 $f(x)=[x\space is \space a\space square\space number]$ 。
此时原式等于：

$\begin{aligned} &\Rightarrow\sum\limits_{T=1}^n\lfloor\frac{n}{T}\rfloor f(T) \\&=\sum\limits_{T=1}^n\lfloor\frac{n}{T}\rfloor [T\space is \space a\space square\space number] \\&=\sum\limits_{T=1}^n\lfloor\frac{n}{T^2}\rfloor \end{aligned}$

时间复杂度 $O(\sqrt n)$ 。

全部评论

推荐最新楼层

11-23 12:48

南京工业大学 Java

看腻了佬，十分钟来看看一名计算机普通双非硕的秋招总结

牛客上充斥着佬们的offer选择和秋招总结，这两天想找些双非硕兄弟们的秋招记录参考参考，能找到的帖子少之又少，趁着今天有时间有心情分享一下供兄弟们参考也作为自己的一个总结😎 始终觉得互联网上也该有更多普通人的生活记录，羡慕佩服佬的同时真的时而也会焦虑迷茫😢 首先介绍下个人bg，南京某学院本计科专业，南京某双非电子信息硕(不过学校有个双一流名头) 简单说硕士期间和大部分人一样做的深度学习，自学java找工作，那么久了水平依旧是苍穹外卖水平hhh，力扣刷了30左右hhh，不过八股个人觉得背的还可以，反正应付面试很ok，大概就是这样 不优秀不突出但普通hhh 适合更多👶 哥们呢我比较爱玩，...

聪敏的鳄鱼在拧螺丝：写的真好，bg一样，看哭了😭😭秋招只进了个南京中小厂后端，看着网上的和身边的一堆人进大厂，总感觉前途渺茫😭

找工作，你会甘心进小厂还是猛冲大厂双非有机会进大厂吗

点赞评论收藏

分享

11-20 17:00

柠檬微趣_人力资源_HR

柠檬微趣25内推

目前很多同学已经被逼签了，局势其实已经开始变化了，各个厂子都有被鸽的岗位，很多hr开始线下捞人，只能说风险和收益并存，趁着11月hr还有捞人指标，没有投的赶紧，最后一波福利期了！中国游戏厂商出海收入前15名，合成手游赛道全球收入最高发行商！实习岗位：策划类：策划实习生运维类：网络运维实习生、主机运维实习生后台开发类：AI实习生、后台实习生(C++)客户端开发类：C++游戏开发实习生(客户端)Unity游戏客户端实习生【正式岗位】1. 客户端类：C++客户端、U3D客户端2. 后端类：C++服务器、Java服务器3. 数据类：大数据开发、数据分析工程师、游戏数据分析师4. 运维类：Linu...

投递柠檬微趣等公司10个岗位 >

点赞评论收藏

分享

10-17 12:16

同济大学 Java

7182oat：快快放弃了然后发给我，然后让我也泡他七天最后再拒掉，狠狠羞辱他一把😋

点赞评论收藏

分享

11-20 19:59

已编辑

湖南工业大学嵌入式工程师

双非本科嵌入式想找工作还有希望吗

微风不断：兄弟，你把四旋翼都做出来了那个挺难的吧

点赞评论收藏

分享

11-18 23:23

中国药科大学外贸业务员

哈哈，终于接到offer了！

这次是来自一家世界500强的外企，真是让我感到无比幸福！找工作真的是靠运气和机遇，面试过程轻松，薪资也很满意。现在终于迎来了转机，心里真是美滋滋的！希望未来的工作能更加顺利！

牛客创作赏金赛

点赞评论收藏

分享

6 收藏评论

全站热榜

正在热议

# 25届秋招总结 #

298437次浏览 2626人参与

# 如果不工作真的会快乐吗 #

58818次浏览 511人参与

# 百度开奖 #

160848次浏览 965人参与

# 地方国企笔面经互助 #

3719次浏览 9人参与

# 美团求职进展汇总 #

1326541次浏览 12443人参与

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

19578次浏览 142人参与

# 北方华创开奖 #

26377次浏览 285人参与

# 正在实习的你，几点下班 #

51536次浏览 384人参与

# 国央企薪资爆料 #

7874次浏览 55人参与

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

991682次浏览 12635人参与

# 提前批简历挂麻了怎么办 #

146317次浏览 1944人参与

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

50793次浏览 400人参与

# 海康威视求职进展汇总 #

398634次浏览 3405人参与

# 米哈游求职进展汇总 #

175754次浏览 1458人参与

# 投递实习岗位前的准备 #

1178821次浏览 18390人参与

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

85006次浏览 845人参与

# 实习生应该准时下班吗 #

167346次浏览 1159人参与

# 得物求职进展汇总 #

66143次浏览 681人参与

# 求职遇到的搞笑事件 #

70635次浏览 576人参与

# 网申一定要掌握的小技巧 #

5302次浏览 53人参与

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

897736次浏览 8007人参与

# 腾讯求职进展汇总 #

195647次浏览 1640人参与

牛客网
牛客企业服务