首页 > 其他分享 >Min-25 筛

Min-25 筛

时间:2024-11-03 16:11:33浏览次数:1  
标签:pr 25 le limits Min text sum prime

Min-25 筛

参考 \(\text{OI-Wiki}\) 和 2018 集训队论文 朱震霆《一些特殊的数论函数求和问题》。

\(\text{Min-25}\) 的本质是埃式筛和数论分块,其实并没有什么高级的技巧。

记 \(x/y = \lfloor \frac{x}{y} \rfloor\),\(pr_k\) 表示第 \(k\) 小的质数,\(\text{lpf}(i)\) 表示 \(i\) 的最小质因数,\(\text{isprime(i)}\) 表示 \(i\) 是否是质数。如无特殊说明以下所有 \(p\) 表示质数。

假设我们要求一个积性函数 \(f\) 的前缀和 \(F(n) = \sum\limits_{i = 1}^{n} f(i)\)。要求 \(f(p)\) 能表示成较少个数的完全积性函数之和。\(f(p^k)\) 可以快速求值。

设 \(F_k(n) = \sum\limits_{i = 2}^{n} [\text{lpf}(i) \ge pr_k] f(i)\)。那么 \(F(n) = F_1(n) + f(1)\),因为 \(f\) 是积性函数,\(f(1) = 1\),即求 \(F_1(n) + 1\)。

考虑如何求一个 \(F_k(n)\),我们枚举最小质因子 \(pr_i\),次数为 \(c\),并特殊处理所有质数,可以得到

\[F_k(n) = \sum\limits_{i \ge k, {pr_i}^2 \le n} \sum\limits_{c \ge 1, {pr_i}^c \le n} f({pr_i}^c) \big{(} F_{i + 1}(n / {pr_i}^c, i + 1) + [c > 1] \big{)} + \sum\limits_{pr_k \le p \le n} f(p) \]

设 \(F_{\text{prime}}(n) = \sum\limits_{p \le n} f(p)\),于是

\[F_k(n) = \sum\limits_{i \ge k, {pr_i}^c \le n} \sum\limits_{c \ge 1, {pr_i}^c \le n} f({pr_i}^c) \big{(} F_{i + 1}(n / {pr_i}^c, i + 1) + [c > 1] \big{)} + F_{\text{prime}}(n) - F_{\text{prime}}(pr_{k - 1}) \]

接下来我们需要求 \(F_\text{prime}(n)\)。对于 \(F_\text{prime}(pr_k)\) 的部分,由于 \(pr_k \le \sqrt n\),可以提前预处理。只需考虑 \(F_\text{prime}(n)\)。

在计算过程中我们只做了 \(n \gets n / x\) 的操作,由于 \(n / x_1 / x_2 / \ldots / x_m = n / (x_1 \times x_2 \times \ldots \times x_m)\)。于是只需对所有 \(m = n / i\),求 \(F_\text{prime}(m)\)。

做一遍整除分块,则 \(m\) 只有不超过 \(2\sqrt{n}\) 种取值,对这些 \(m\) 筛出 \(F_\text{prime}(m)\) 的点值即可。

一般情况下,\(f(p)\) 是一个关于 \(p\) 的低次多项式,可以表达为 \(f(p) = \sum\limits_{i} a_ix^i\)。

考虑分离每个 \(x^i\) 的贡献,设 \(g(p) = p^i\),类似的设一个 \(G_{\text{prime}}(n) = \sum\limits_{p = 2} g(p)\)。则最后可以用若干个 \(G_\text{prime}\) 合并出 \(F_{\text{prime}}\),此时再分别补上 \(a_i\) 的系数。

现在只需求 \(G_{\text{prime}}\)。注意到 \(g(p)\) 是完全积性函数。设 \(G_{k}(n) = \sum\limits_{i = 2}^{n} [\text{isprime}(i) \vee \text{lpf}(i) \ge pr_k] g(i)\),即埃式筛 \(k\) 轮后剩下的数 \(g(i)\) 之和。对于一个合数 \(x\),必有 \(\text{lpf}(x) \le \sqrt x\)。于是 \(G_\text{prime} = G_{\lfloor \sqrt{n} \rfloor}\)。

然后我们可以写出一个 \(G_k\) 的递推式:

\[\begin{align} G_k(n) = \ & G_{k - 1}(n) - \sum\limits_{i = 2}^{n} [\lnot \text{isprime}(i) \wedge \text{lpf}(i) = pr_k] g(i) \\ & G_{k - 1}(n) - f(pr_k)\big{(}G_{k - 1}(n / pr_k) - G_\text{prime}(pr_{k - 1}) \big{)} \end{align} \]

其中由于 \(pr_k \le \sqrt n\),\(G_\text{prime}(pr_k)\) 同样可以预处理。最后从小到大枚举每个 \(k\) 做转移即可。

求出 \(F_\text{prime}\) 后可以直接递归算 \(F_k(n)\)。

时间复杂度分析我不会。参考论文的话,递推做 \(F_\text{prime}\) 部分时间复杂度 \(O(\frac{n^{\frac{3}{4}}}{\log n})\),递归算 \(F_k(n)\) 时间复杂度 \(O(n^{1 - \epsilon})\),总时间复杂度就是两者相加。

\(\text{Min-25}\) 的题目基本上都比较板,这里就不讲了。

标签:pr,25,le,limits,Min,text,sum,prime
From: https://www.cnblogs.com/estruct/p/18523549

相关文章

  • 2024-2025-1 20241301 《计算机基础与程序设计》第六周学习总结
    |这个作业属于哪个课程|<2024-2025-1-计算机基础与程序设计(https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP)>||这个作业要求在哪里|<2024-2025-1计算机基础与程序设计第六周作业](https://www.cnblogs.com/rocedu/p/9577842.html#WEEK06)>||这个作业的目标|<夯实基础,......
  • 2024-2025-1 20241312《计算机基础与程序设计》第6周学习总结
    这个作业属于哪个课程<班级的链接>(如2024-2025-1-计算机基础与程序设计)这个作业要求在哪里<作业要求的链接>(如2024-2025-1计算机基础与程序设计第六周作业)这个作业的目标Polya如何解决问题简单类型与组合类型复合数据结构查找与排序算法算法复杂度递归代码......
  • 2024-2025-1 20241415 《计算机基础与程序设计》第六周学习总结
    2024-2025-120241415《计算机基础与程序设计》第六周学习总结作业信息这个作业属于哪个课程2024-2025-1-计算机基础与程序设计这个作业要求在哪里2024-2025-1计算机基础与程序设计第六周作业这个作业的目标Polya如何解决问题、简单类型与组合类型、复合数据结构......
  • 2024-2025-1 20241407《计算机基础与程序设计》第六周学习总结
    这个作业属于哪个课程[2024-2025-1计算机基础与程序设计](https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP)这个作业要求在哪里2024-2025-1计算机基础与程序设计第六周作业这个作业的目标学习Polya如何解决问题,简单类型与组合类型,复合数据结构,查找与排序算法......
  • 2024-2025-1 20241423 《计算机基础与程序设计》第六周学习总结
    作业信息这个作业属于哪个课程2024-2025-1-计算机基础与程序设计(https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP)这个作业要求在哪里2024-2025-1计算机基础与程序设计第六周作业这个作业的目标学习Polya如何解决问题、简单类型与组合类型、复合数据结构、......
  • 【热门主题】000025 单片机:科技世界的微型大脑
    前言:哈喽,大家好,今天给大家分享一篇文章!并提供具体代码帮助大家深入理解,彻底掌握!创作不易,如果能帮助到大家或者给大家一些灵感和启发,欢迎收藏+关注哦......
  • 2024-2025-1 20241319 《计算机基础与程序设计》第六周学习总结
    作业信息这个作业属于哪个课程2024-2025-1-计算机基础与程序设计这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK06这个作业的目标Polya如何解决问题简单类型与组合类型复合数据结构查找与排序算法算法复杂度递归代码安全作业正文......
  • 2024-2025 20241323 第六周学习总结
    这个作业属于https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP这个作业要求https://www.cnblogs.com/rocedu/p/9577842.html#WEEK01作业正文https:https://www.cnblogs.com/gly03/p/18523229教材学习内容总结一、简单类型与组合类型(一)简单类型简单类型(PrimitiveType......
  • 2024-2025-1 20241320 《计算机基础与程序设计》第6周学习总结
    2024-2025-120241320《计算机基础与程序设计》第6周学习总结作业信息|这个作业属于哪个课程https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP|这个作业要求在哪里|https://www.cnblogs.com/rocedu/p/9577842.html#WEEK06|这个作业的目标|Polya如何解决问题简单类......
  • 2024-2025-1 学号20241315《计算机基础与程序设计》第六周学习总结
    作业信息这个作业属于哪个课程2024-2025-1-计算机基础与程序设计这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK06这个作业的目标Polya如何解决问题简单类型与组合类型复合数据结构查找与排序算法算法复杂度递归代码安全作业正文......