接卷积
杜教筛
为了改模拟考试题被迫学的
参考这篇blog
设有积性函数 \(f(x)\), 求 $ \sum\limits_{i = 1}^ n {f(x)} $。
当数据范围太大(如[1, 1e9])时无法直接计算，要考虑使用复杂度小于先线性的做法。
我们想到数论分块，但大多数时候无法直接使用，考虑找个函数 \(g(n)\) 与 \(f(n)\) 卷起来，得到更好维护的式子。
我们设 \(S(n)=\sum\limits_{i=1}^{n}f(i)\)
设 \(g(n)\) 和 \(f(n)\) 卷起来后的前缀和：
\[\begin{aligned} &= \sum\limits_{i = 1}^{n} \sum\limits_{d | i} f(d) g(\frac{i}{d}) \\ &= \sum\limits_{d = 1}^{n}{g(d)} \sum\limits_{i = 1}^{\lfloor \frac{n}{d}\rfloor } f(i) \\ &= \sum\limits_{d = 1}^{n} g(d) S(\left\lfloor \frac{n}{d} \right\rfloor) \end{aligned} \]
考虑 \(g(1)S(n)\) 发现:
\[\begin{aligned} g(1)S(n) &= \sum\limits_{i = 1}^{n}{g(i)S(\left\lfloor\frac{n}{i}\right\rfloor)} – \sum\limits_{i = 2}^{n}{g(i)S(\left\lfloor\frac{n}{i}\right\rfloor)} \\ &= \sum\limits_{i = 1}^{n}{(f * g)(i)} – \sum\limits_{i = 2}^{n}{g(i)S(\left\lfloor\frac{n}{i}\right\rfloor)} \end{aligned} \]
则得到杜教筛的模板式：
\[\begin{aligned} g(1)S(n) &= \sum\limits_{i = 1}^{n}{(f * g)(i)} – \sum\limits_{i = 2}^{n}{g(i)S(\left\lfloor\frac{n}{i}\right\rfloor)} \end{aligned} \]
之后的工作就是找到那个合适的 \(g\) 函数
要求可以在复杂度 \(O(1)\) 或 \(O(\sqrt{n})\)的情况下求出 \(\sum\limits_{i=1}^{n}(f*g)(i)\) ，否则无法递归求出解
找到\(g\)后剩下的就是数论分块加递归求解加记忆化了
原文地址：http://www.cnblogs.com/Eakang/p/16908082.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
