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-20 00:03

河北大学 Java

腾讯的待遇真的挺不错的

在求职的路上，看到腾讯的薪资开到30k，心里真是五味杂陈。作为互联网的老大，腾讯的薪酬确实不含糊，但这也让不少人感到压力山大，尤其是那些被倒挂的同行们。虽然我也在努力寻找机会，但看到这些数字，心里难免有些失落。尤其是那些工作强度高的岗位，朝十晚八的作息让我觉得身体承受不住。希望未来能有更好的机会，让我也能在这个竞争激烈的市场中找到属于自己的位置。

牛客创作赏金赛

点赞评论收藏

分享

11-18 17:02

北京理工大学算法工程师

我的人生步伐是不是有点快

感觉我可能是我们这届人生进程最快的了，入职3个月左右干了好多大事。 我的timeline：7月初：入职百度7月上旬：参与公司集中一周培训，了解到了公司文化、业务方向、公司战略、职业发展方向，印象最深的是在零度突破这个landing培训中，整个培训过程很有意思，类似王牌对王牌那种综艺，仿佛我们化身成沈腾或者节目嘉宾来一起做游戏，最后还要不同业务部门小伙伴完成一个课题，我们当时的课题是AI智能体，我们一组的有产品、有管理、有rd，做项目的交流过程中还是很有收获的，不光有了更全局的视角，还认识了好多小伙伴，包括我现在的女朋友。7月中下旬：跟着给我们分配的mentor做项目，虽然只是一个小模块，但是都...

在做测评的杨桃很想去东北泡澡：我劝你删了，因为我一个都还没有

百度成长空间 414人发布百度工作体验

点赞评论收藏

分享

10-25 00:32

这种简历应该怎么投秋招，摆了四年基本属于啥都不会，救救

香梨想要offer：感觉考研以后好好学后面能乱杀，目前这简历有点难

点赞评论收藏

分享

昨天 19:04

已编辑

湖南工商大学 Java

大三，普通一本，想实习，求建议

明年春招想找实习还有机会吗，怎么准备去丰富简历啊，我太想进步了，太想进大厂了

点赞评论收藏

分享

11-20 08:16

华为_算法工程师

学历垫底，绩效拿A，在华为是什么体验？

学历垫底，绩效拿A，在华为是什么体验？本文是2024年11月2日公众号来知晓原创首发文章。我两手空空，但可以打败风。——少年，郑皓元，8岁读者朋友你好，欢迎来到来知晓。本期继续聊聊职场成长话题，分享下我在华为绩效拿A的工作体验和几点思考。在菊厂，为啥要积极冲击拿A？一方面，菊厂一直鼓励拉开差距，鼓励火车头文化，老板官宣火车跑得快，全靠车头带。于是，体现在各种激励、荣誉上都有较大区别。另一方面，如果你享受这种竞争机制，带来的个人成长的话，应该也会主动想去冲击绩效A。举个实例，我问上期提到的那位清华同事H，你来我司后感觉压力咋样？同事H说，我来还是想要有点压力的，不然不会来华为了。我不由想，积极主...

华为工作强度 810人发布华子oc时间线机械人还在等华为开奖吗？

点赞评论收藏

分享

6 收藏评论

全站热榜

正在热议

# 25届秋招总结 #

296123次浏览 2598人参与

# 美团求职进展汇总 #

1325895次浏览 12438人参与

# 百度开奖 #

158972次浏览 955人参与

# 地方国企笔面经互助 #

3679次浏览 8人参与

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

58617次浏览 507人参与

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

19271次浏览 140人参与

# 阿里云管培生offer #

15941次浏览 291人参与

# 国央企薪资爆料 #

7381次浏览 53人参与

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

50435次浏览 398人参与

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

398438次浏览 3405人参与

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

51351次浏览 382人参与

# 米哈游求职进展汇总 #

175632次浏览 1456人参与

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

1178568次浏览 18387人参与

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

84932次浏览 844人参与

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

991133次浏览 12632人参与

# 得物求职进展汇总 #

66056次浏览 679人参与

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

167299次浏览 1159人参与

# 求职遇到的搞笑事件 #

70522次浏览 575人参与

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

5295次浏览 52人参与

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

897277次浏览 8005人参与

# 腾讯求职进展汇总 #

195484次浏览 1637人参与

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

146205次浏览 1944人参与

牛客网
牛客企业服务