杜教筛

比眉伴天荒 2023-08-17 16:33 66阅读 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 条评论，66人围观）

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

相关阅读

相关欧拉筛&&埃氏筛

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

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

相关杜教筛

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

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

相关【素数判断】埃氏筛法和欧拉筛法（线性筛法）

埃氏筛法埃氏筛法的原理是：给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔

本是古典何须时尚/ 2023年01月10日 10:28/ 0 赞/ 124 阅读

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

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

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

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

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

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

相关素数筛法

//暴力枚举素数筛法 o(n 根号n) for(int i=2;i<=n;i++){ bool g=0; for(int j=2;jj<

╰+哭是因爲堅強的太久メ/ 2022年04月04日 10:54/ 0 赞/ 235 阅读

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

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

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

相关素数筛C++

埃拉托斯特尼筛法（sieve of Eratosthenes ）是古希腊数学家埃拉托斯特尼发明的计算素数的方法。对于求解不大于n的所有素数，我们先找出sqrt(n)内的所有素

向右看齐/ 2022年02月09日 11:15/ 0 赞/ 255 阅读

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

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

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

相关 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 赞/ 149 阅读