首页 > 其他分享 >杜教筛

杜教筛

时间:2023-07-13 21:13:56浏览次数:23  
标签:lfloor frac limits sum sqrt 杜教 aligned

杜教筛

令 \(f(x)\) 为某个积性函数,\(s(n)=\sum\limits_{i=1}^nf(i)\),我们构造另一干函数 \(g\) 算 \(f*g\) 的前缀和。

\[\begin{aligned} \sum\limits_{i=1}^n(f*g)(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}g(d)f(\dfrac{i}{d})=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{d}\right\rfloor}f(i)=\sum\limits_{d=1}^ng(d)s(\left\lfloor\dfrac{n}{d}\right\rfloor) \end{aligned} \]

我们的目标是 \(s(n)\)

我们发现:

\[\begin{aligned} g(1)s(n)=\sum\limits_{i=1}^n(f*g)(i)-\sum\limits_{d=2}^ng(d)s(\left\lfloor\dfrac{n}{d}\right\rfloor) \end{aligned} \]

我们需要算出 \((f*g)\) 的前缀和,通过对减号右边数论分块,我们需要算 \(g\) 的前缀和,我们还需要算出 \(g(1)\) 。所以关键在于 \(g\) 函数的选取。

例子

  • \(\sum\limits_{i=1}^N\mu(i)\)

不难发现我们这里应该选 \(g\) 函数为 \(I\) 。然后 \(g\) 的前缀和为 \(n\),\(f*g\) 的前缀和是 \(1\)。

  • \(\sum\limits_{i=1}^N\phi(i)\)

不难发现我们还是选 \(g\) 为 \(I\)。然后 \(g\) 的前缀和为 \(n\),\(f*g\) 的前缀和为 \(\dfrac{n(n+1)}{2}\)

  • \(\sum\limits_{i=1}^N\phi(i)\times i\)

考虑有:

\[\begin{aligned} (f*g)(n)=\sum\limits_{d|n}f(d)g(\dfrac{n}{d})=\sum\limits_{d|n}\phi(d)\times d\times g(\dfrac{n}{d}) \end{aligned} \]

考虑把 \(d\) 消掉,所以我们不妨令 \(g=id\),这样这个题就结束了。

  • \(\sum\limits_{i=1}^N\phi(i)\times i^2\)

我们还是和上面一样,把它拆开:

\[\begin{aligned} (f*g)(n)=\sum\limits_{d|n}f(d)g(\dfrac{n}{d})=\sum\limits_{d|n}\phi(d)\times d^2\times g(\dfrac{n}{d}) \end{aligned} \]

我们本着把 \(d^2\) 消去的思路,不妨令 \(g(x)=x^2\),这样就可以了。

复杂度证明

设 \(k\) 以前的部分我们预处理,所以杜教筛的复杂度为:

\[\sum\limits_{i=1}^{\frac{n}{k}}\sqrt{\left\lfloor\frac{n}{i}\right\rfloor}\le \int_{1}^{\frac{n}{k}}\sqrt{n}x^{-\frac{1}{2}}dx=O(\frac{n}{\sqrt{k}}) \]

所以总复杂度应该为 \(O(\frac{n}{\sqrt{k}}+k)\),显然 \(k=n^{\frac{2}{3}}\) 的时候最优,所以总复杂度为 \(O(n^\frac{2}{3})\) 。

相反,如果不预处理的话,相当于要对所有可能的 \(\lfloor\frac{n}{i}\rfloor\) 做一个整数分块,一共有 \(O(\sqrt{ n})\) 种取值,我们不妨认为这 \(O(\sqrt n)\) 种取值为 \(\lfloor\frac{n}{1}\rfloor,\lfloor\frac{n}{2}\rfloor,\cdots,\lfloor\frac{n}{\sqrt n}\rfloor\),实际上,整数分块得到的数不会超过 \(2\sqrt{ n}\) 个,用这 \(\sqrt{n}\) 个最大的值来估算显然是正确的。

所以时间复杂度约为:

\[\int _1^{\sqrt{n}}\sqrt{\frac{n}{x}}dx=O(n^{\frac{3}{4}}) \]

标签:lfloor,frac,limits,sum,sqrt,杜教,aligned
From: https://www.cnblogs.com/HeNuclearReactor/p/17552186.html

相关文章

  • 杜教筛
     杜教筛起源于中学信息学队员杜瑜皓它结合了三种算法,分别是:整除分块,狄利克雷卷积和线性筛它主要是求解n较大时的积性函数的值它的时间复杂度是O(n^(2/3)),小于O(n)杜教筛在竞赛中很难出现例题:P4213【模板】杜教筛(Sum)这是一道模板题,给出代码#include<bits/stdc++.h>#def......
  • 杜教筛 & Min25 筛
    发现这个东西很容易忘,果然还是理解不够吧,写一篇博客方便以后复习。杜教筛目的是要求\(S(n)=\sum_{i=1}^nf(i)\)。我们需要构造两个函数\(g,h\)满足\(f*g=h\),其中\(h\)是一个积性函数且能快速求和。考虑求\(\sum_{i=1}^n\sum_{d|i}f(d)g(\dfrac{i}{d})=\sum_{i=1}......
  • 杜教筛 & Powerful Number 筛
    迪利克雷卷积对于数论函数\(F\),\(G\),我们定义迪利克雷卷积的结果\(H=F*G\)为\[H_n=\sum_{d\midn}F_dG_\frac{n}{d}\]有些好的性质,比如:对于积性函数\(F\)与\(G\),其迪利克雷卷积\(F*G\)也是积性函数;而在迪利克雷卷积的意义下,积性函数\(F\)的逆也是积性函数(逆满足\(F......
  • 【学习笔记】杜教筛
    如果我们要求一个积性函数\(f(x)\)的前缀和,可以用杜教筛在\(O(n^{\frac{2}{3}})\)的复杂度求出。具体地,构造函数\(g(x)\)和函数\(h(x)\),使得$h=f*g$,要求的式子是\(S(n)=\sum\limits_{i=1}^{n}f(i)\)。开始推式子。\[\sum\limits_{i=1}^{n}h(i)=\sum\limits_{i=1}^{......
  • 浅析数论--埃氏筛/欧拉筛/杜教筛
    \(\mathcal{0x01绪论}\)\(\mathcal{质数的判定试除法or六倍原理}\)一个合数的约数总是成对出现的,如果\(d|n\)(\(d\)能被\(n\)整除),那么\((n/d)|n\),因此我们判断一个......
  • [bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)
    题面设为的约数个数,给定,求题目分析有这样一个结论这道题就是下面这道题的数据增强版,那么这个结论的证明就不再赘述,请自行查看下面的(蒟蒻)博客​​传送门:[SDOI2015][bz......
  • [51Nod 1227] 平均最小公倍数 (杜教筛)
    题目描述求题目分析这道题其实是​​[51Nod1238]最小公倍数之和题解​​的简化版,或者说是本质…就直接上公式了令,则此处有一个常识证明如下当时,若,所以与互质的......
  • [51Nod 1237] 最大公约数之和 (杜教筛+莫比乌斯反演)
    题目描述求题目分析乍一看十分像裸莫比乌斯反演,然而的范围让人望而却步于是先变化一下式子枚举令k=Td则此时可以整除分块优化,每次算出相等的上下界后用莫比乌斯反演计......
  • [HDU 5608]Function(莫比乌斯反演 + 杜教筛)
    题目描述有求只有最多组数据题目分析如此一来就可以杜教筛了,然而仅仅这样还是会T,于是我们在想一想如何筛出前面一部分的值令,根据莫比乌斯反演于是用筛出前项就行了......
  • 莫比乌斯反演与杜教筛
    莫比乌斯反演与杜教筛积性函数定义对于一个数论函数\(f\),若满足\(\forall(a,b)=1\)都有\(f(ab)=f(a)f(b)\),那么称\(f\)为积性函数。例子常见的积性函数有很多,......