杜教筛

比眉伴天荒 2023-08-17 16:33 85阅读 0赞

暑期的学习开始了，今天先来讲一下杜教筛吧（反演的坑以后再填。。。

# 核心公式： #

我们设\\(\\begin\{aligned\}S(n)=\\sum\_\{i=1\}^\{n\}(f \* g)\_ \{(i)\}\\end\{aligned\}\\)，且\\(g\\)为一个完全积性函数。

那么可以得到：

\\(\\begin\{aligned\}\\sum\_\{i=1\}^n((f\* 1)\_ \{(i)\}\\times g)=\\sum\_\{i=1\}^ng(i)\\times S(\\lfloor\\frac n i\\rfloor)\\end\{aligned\}\\)

证明：

\\(\\begin\{aligned\}\\sum\_\{i=1\}^n((f\* 1)\_ \{i\}\\times g)&=\\sum\_\{i=1\}^ng(i)\\times\\sum\_\{d|i\}f(d)\\\\&=\\sum\_\{d=1\}^n\\sum\_\{i=1\}^\{\\lfloor\\frac n d\\rfloor\}g(id)\\times f(d)\\\\&=\\sum\_\{d=1\}^ng(i)\\times g(d)\\times f(d)\\\\&=\\sum\_\{d=1\}^ng(d)\\times S(\\lfloor\\frac n d\\rfloor)\\end\{aligned\}\\)

证毕

# 具体实现： #

*  \\(\\mu\\)函数求前缀和：
    
    根据\\(\\mu\* 1=\\epsilon\\)，将\\(\\epsilon\\)作为\\(S\\)、\\(\\mu\\)作为\\(f\\)、\\(1\\)作为\\(g\\)代入上述公式，得到：\\(\\begin\{aligned\}\\sum\_\{i=1\}^n\\epsilon(i)=\\sum\_\{d=1\}^n1(d)\\times S(\\lfloor\\frac n d\\rfloor)\\end\{aligned\}\\)
    
    把\\(d=1\\)拿出来，再化简得：\\(\\begin\{aligned\}1=S(n)+\\sum\_\{d=2\}^nS(\\lfloor\\frac n d\\rfloor)\\end\{aligned\}\\)
    
    移个项，得：\\(\\begin\{aligned\}S(n)=1-\\sum\_\{d=2\}^nS(\\lfloor\\frac n d\\rfloor)\\end\{aligned\}\\)
 *  \\(\\varphi\\)函数求前缀和：
    
    根据\\(\\varphi\* 1=id\\)得到：
    
    \\(\\begin\{aligned\}S(n)=\\frac\{n\\times(n+1)\}\{2\}+\\sum\_\{d=2\}^nS(\\lfloor\\frac n d\\rfloor)\\end\{aligned\}\\)

转载于:https://www.cnblogs.com/WR-Eternity/p/11153806.html

发表评论取消回复

表情：

评论列表（有 0 条评论，85人围观）

还没有评论，来说两句吧...

相关阅读

相关欧拉筛&&埃氏筛

数论——欧拉筛、埃氏筛 `记录一点关于数论的知识，该知识点本身不难，主要是学习一下思想~` -------------------- 文章目录数论——欧

向右看齐/ 2024年03月30日 12:54/ 0 赞/ 101 阅读

相关素数筛

目录题目思路1 思路2 思路3 题目给定一个正整数n(2≤n≤10000)，先输出2~n之间的素数个数

拼搏现实的明天。/ 2023年10月06日 16:35/ 0 赞/ 68 阅读

相关质数 AcWing 868. 筛质数线性筛

质数 AcWing 868. 筛质数原题链接 [AcWing 868. 筛质数][AcWing 868.] 算法标签数学知识质数线性筛法筛法求素数

水深无声/ 2023年09月28日 11:35/ 0 赞/ 30 阅读

相关杜教筛

暑期的学习开始了，今天先来讲一下杜教筛吧（反演的坑以后再填。。。核心公式：我们设\\(\\begin\{aligned\}S(n)=\\sum\_\{i=1\}^\

比眉伴天荒/ 2023年08月17日 16:33/ 0 赞/ 86 阅读

相关 Eratosthenes筛

什么是Eratosthenes筛？ (What is Sieve of Eratosthenes?) Sieve of Eratosthenes is an ancien

忘是亡心i/ 2023年03月05日 09:46/ 0 赞/ 16 阅读

相关计蒜客蒜头君的兔子（神奇的杜教板子）

[题目传送门][Link 1] 下面的代码别问我为什么这么写，我也不会，只是听说能解决一切线性递推式只要把前面几项先处理出来就可以了，一般到50项应该就没问题了

雨点打透心脏的1/2处/ 2022年05月15日 11:47/ 0 赞/ 339 阅读

相关 51Nod 1242 斐波那契数列的第N项 ——————杜教筛，BM板子

1242 斐波那契数列的第N项基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题收藏关注斐波那契数列的定义如下： F ( 0 )

不念不忘少年蓝@/ 2022年05月09日 10:18/ 0 赞/ 150 阅读

相关杜教板子（BM）线性递推式

据说这个模板可以解决任何线性递推式，听说是杜教的，只要我们手推递推式的前几项，然后扔进这个板子就哦了，我的天，前几项丢的越多越好，8个以上就稳了(打脸了，有的题还是要多要一点）

╰半夏微凉°/ 2022年04月04日 10:53/ 0 赞/ 147 阅读

相关 BZOJ 4176: Lucas的数论莫比乌斯反演 + 杜教筛

Description 去年的Lucas非常喜欢数论题，但是一年以后的Lucas却不那么喜欢了。在整理以前的试题时，发现了这样一道题目“求Sigma(f(i)),其中

短命女/ 2021年11月17日 16:26/ 0 赞/ 277 阅读

相关 SCUT - 114 - 作业之数学篇 - 杜教筛

[https://scut.online/p/114][https_scut.online_p_114] \\(A(n)=\\sum\\limits\_\{i=1\}^\{n

﹏ヽ暗。殇╰゛Y/ 2021年11月13日 18:58/ 0 赞/ 169 阅读