2021-12-20 14:26 北京大学 C++

关注

题解 | #RdecAgl#

RdecAgl

https://ac.nowcoder.com/acm/contest/11195/E

套路题的嵌套。

首先只用对每个 $i=1,2, \dots n$ 算 $\sum_T \gcd(T_1, \dots, T_i)$ ，之后随便组合一下就能算出答案。

\sum_T \gcd(T_1, \dots, T_i) \\ = \sum_{T} \sum_{d| \gcd(T_1, \dots, T_i) } \varphi(d) \\ = \sum_{d=1}^m \varphi(d) (\lfloor m/d \rfloor)^i

考虑数论分块，需要对所有 $\lfloor m/d \rfloor$ 相同的 $d$ 求 $\varphi(d)$ 的和，这一步可以用你喜欢的筛法(如min25筛)完成。

之后问题变成了对 $i=1,2, \dots n$ 求 $\sum_{j=1}^G a_j b_j^i$ ， $G \approx 2 \sqrt{m}$ 。

$\sum_{j=1}^G a_j b_j^i=[x^i](\sum_{j=1}^G \dfrac{a_j}{1-b_jx})$ ，所以只需分治NTT即可。

全部评论

推荐最新楼层

03-24 15:58

门头沟学院 Java

3-24-梦尔达-二面

测试的常见类型有哪些？看你用了部署ai，请问你用它干了什么？你在测试当中是怎么利用ai的？缺陷的生命周期？数据库断言解释一下？如何分析sql语句？你的自动化测试框架相比postman、apifox有什么优点？有用过openclaw吗？详细说一下遇见一个问题不确定是不是bug该怎么办？自己的职业规划？能实习多久？你手上有多少offer了？投简历的时候是只投杭州还是北上广深都投？为什么选择杭州？二面一个男的面试的，答得一般化，这个面试官有点注重ai的使用，面了15min，在问到你在测试当中如何利用ai的时候回答的不太好，面试官说了就这些吗？感觉要挂#牛客AI配图神器#

查看14道真题和解析

点赞评论收藏

昨天 18:03

门头沟学院机器学习

阿里0325笔试

今天得空review了一下昨晚的笔试，AI研发方向的，整体上有一定的难度，感觉自己答得还可以吧，期待给个面试机会 20 道选择 + 3 道编程 + 1 道 Prompt，T1 签到，T2 贪心一眼秒，T3 是个数位 DP 有点东西，T4 Prompt 题考的是让 AI 算出租车费。 选择题概览 选择题一半 AI 一半 CS 基础，AI 方向的占比还是挺高的。 AI/Agent 相关的大概考了这些：Transformer 的 teacher forcing 训练推理差异、MHA/MQA/GQA 注意力机制对比、LangChain 和 LangGraph 的关系、ReAct 的机制边界、multi...

阿里笔试

点赞评论收藏

03-21 21:53

四川大学 Java

为什么简历挂了

想找暑假java后端实习 但是简历过不了 大佬们能帮忙看看嘛 谢谢！

点赞评论收藏

02-25 17:58

吉首大学张家界学院 Python

这种简历可以吗，大四

这种简历可以吗想进个小公司就可以了，只想有个稳定的工作有点结巴

最喜欢秋天的火龙果很...：第一份工作一定要往大的去，工资低点没事。后面换工作会更好找，即使你去小公司，你也不可能不会换工作的。所以找大的去

点赞评论收藏

03-20 16:56

门头沟学院 Java

Redis 内存碎片

ps：如果这篇帖子对于还在找工作和找实习的你有所帮助，可以关注我，给本贴点赞、评论、收藏并订阅专栏；同时不要吝啬您的花花核心结论：Redis内存碎片是已分配但未被使用的零散内存块，常见于频繁增删改场景，会导致内存浪费、OOM风险，需通过INFO memory监控并主动整理。一、什么是内存碎片？内存碎片指Redis已向操作系统申请到的内存（used_memory_rss）中，未被有效利用的空闲小块。这些碎片虽总存在，但因不连续、大小不匹配，无法被新数据复用，最终表现为：实际存数据内存（used_memory）远小于操作系统分配内存（used_memory_rss）内存利用率下降，甚至触发maxm...

Redis生产

点赞评论收藏

全站热榜

创作者周榜

正在热议