Loading...

杜教筛 学习笔记

check评论:0 条 remove_red_eye浏览量:129 change_historyTags:编程学习笔记
作者 : Decoration date_range日期 : 2019-07-30

前置知识1

数论函数:定义域为正整数的函数

积性函数:对于$p,q\in N^*$以及积性函数$f$,如果$gcd(p,q)=1$,则$f(p*q)=f(p)*f(q)$

完全积性函数:对于$p,q\in N^*$以及完全积性函数$f$,$f(p*q)=f(p)*f(q)$

常见的积性函数:$\mu,\varphi,\sigma$

常见的完全积性函数:$1,I,\varepsilon,id$

完全积性函数的定义是:$1(n)=1,I^k(n)=n^k,\varepsilon(n)=[n=1],id(n)=n$

因为$\sum\limits_{i=1}^n \mu(i)=[n=1]$,故$\mu * 1 =\varepsilon$

因为$\sum\limits_{i=1}^n \varphi(i)=n$,故$\varphi*1=\varepsilon$

因为$\varphi*\mu*1=id*\mu,\varphi*\varepsilon=id*u$,故$\varphi=id*u$

前置知识2

  • 莫比乌斯反演

因为$f*\mu=g*1*\mu=g*\varepsilon=g$

所以$1$的逆是$\mu$

故$f(n)=\sum\limits_{d|n} g(d),g(n)=\sum\limits_{i=1}^n f(i)\mu(\frac{n}{i})$

杜教筛

设$S(n)=\sum\limits_{i=1}^n f(i)$

再选另一积性函数$g$,则$\sum\limits_{i=1}^n (f*g)(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}f(d)g(\lfloor\frac{i}{d}\rfloor)$

原式可化为$\sum\limits_{i=1}^ng(i)\sum\limits_{d=1}^{\lfloor\frac{n}{i}\rfloor}f(i)=\sum\limits_{i=1}^n g(i) S(\lfloor\frac{n}{i}\rfloor)$

考虑怎么求$g(1)S(n)$,注意到$g(1)S(n)=\sum\limits_{i=1}^n(f*g)(i)-\sum\limits_{i=2}^ng(i)S(\lfloor\frac{n}{i}\rfloor)$

只要快速算出$(f*g)(i)$和$g(i)$的前缀和,即可整除分块,此时复杂度为$O(n^{\frac{3}{4}})$

如何进一步优化?

可以先筛前$m$个答案,此时复杂度$T(n)=m+\sum\limits_{i=1}^{\lfloor\frac{n}{m}\rfloor}\sqrt{\frac{n}{i}}=O(m+\frac{n}{\sqrt m})$

当$m=n^{\frac{2}{3}}$时,复杂度最低为$O(n^{\frac{2}{3}})$

常见的题目,求$\sum\limits_{i=1}^n \mu(i)$

因为$\mu*1=\varepsilon$

所以令$S(n)=\sum\limits_{i=1}^n \mu(i),g(i)=1(i)$,由杜教筛公式可知$S(n)=\frac{\sum\limits_{i=1}^n (\mu*g)(i)-\sum\limits_{i=2}^ng(i)S(\lfloor\frac{n}{i}\rfloor)}{g(1)}$

其中$\sum\limits_{i=1}^n (\mu*g)(i)$显然等于$\varepsilon(1)=1$,$\sum\limits_{i=2}^ng(i)=\sum\limits_{i=2}^n 1$,$g(1)=1$

故$S(n)=1-\sum\limits_{i=2}^n S(\lfloor\frac{n}{i}\rfloor)$,整除分块即可

例题plus

给定$n(n\leq 10^{10})$,求出$\sum\limits_{i=1}^n i\mu(i)$

令$g(i)=i$,即$g$为$id$函数,则$(g*f)(n)=[n=1]$

所以该函数前缀和为$1$,$\sum\limits_{i=1}^n g(i)=\frac{n^2+n}{2}$

然后整除分块即可

chevron_left 题解 CF993E
题解--顺序对齐 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名