「关于一种处理关于$p$成多项式的数论函数筛法」

时间:2022-03-06 09:09:57

  张博航原知乎网址

  张博航原博客网址

引入:

  给一个完全积性函数$f$,求其前缀和

  $$S(n)=\sum_{i=1}^nf(i)$$

初步思考:

  考虑由于所求函数为完全积性函数,我们很容易用一个线性筛在$O(n)$的时间负责度内解决问题。

  但是往往这类问题要求更加优秀的时间负责度,那么线筛便不能满足我们的需要,我们需要更加优秀的做法。

  我们考虑一种最基础的筛法:埃拉托斯特尼筛法。

  在这种筛法的思路中,我们只需要枚举$\sqrt n$以内的质数,那么我们是否可以引入这种想法呢?

进一步思考:

  我们考虑将$S(n)=\sum_{i=1}^n f(i)$换成与质数有关的表达形式。

  我们设$\tau(x) = x的最大质因子$。

  那么

  $$S(n) = \sum _{i=2}^n\sum_{\tau(i)<p,i*p<=n}f(ip) + \sum_{i=2}^nf(i)[\tau^2(i)|i] + f(1) + \sum_{p=2}^n f(p)$$

  $$\because \forall a,b\; f(ab)=f(a)f(b)$$

  $$\therefore S(n)=\sum_{i=2}^nf(i)\sum_{\tau(i)<p,ip<=n,p==\tau (p)}f(p)+\sum_{i=2}^nf(i)[\tau^2(i)|i]+f(1)+\sum_{p=2}^nf(p)$$

  我们来看这个式子。

  我们发现前两部分枚举的$i$所含质数$p$必然$p<=\sqrt n$。

  那么我们使用DFS来枚举这些$i$会发现枚举量为:$$n-\sum_{i=\sqrt n+1,i=\tau(i)}^n \lfloor \frac{n}{i} \rfloor$$

  这个式子我并不会算……

  但是通过张博航的博客,这个式子的结果是约等为$\frac{n^{\frac{3}{4}}}{ln n}$存在一定的常数。

思考算法设计:

  那么问题就变成了如果去求$\sum_{\tau(i)<p,ip<=n}f(p)$以及$\sum_{p=2,p=\tau(p)}f(p)$。

  我们发现后者其实是可以看作于前者是一类的。

  那么设$S'(n)=\sum_{p=2,p=\tau(p)}f(p)$,即上式为$S'(\frac{n}{i})-S'(\tau(i))$来表示的。

  由于除法分块我们可以知道$\lfloor \frac{n}{i} \rfloor$取值仅有$\sqrt n$级别个,同时$\tau(i) <=\sqrt n$。

  那么我们设$$a_i = S'(i),b_i=S'(\frac{n}{i}),i\leqslant \sqrt n$$

  那么考虑如何求出$S'$。

  我们先将所有数都看做质数,那么此后我们从小到大枚举一个每个小于$\sqrt n$的质数$p$,那么

  $$S'(i)=S'(i)-f(p)(S'(\frac{i}{p})-S'(p-1))$$

  考虑用数学归纳法证明:

  首先当$p==2$时,此式显然得到的是去掉所有含“2”因子的合数。

  那么设此式在之前质数中都是正确的,此时枚举到了$p$。同时设$\zeta i = i的最小质因数$

  那么我们考虑此时

    $S'(x)=\sum_{i=2,i=\tau(p),i<p}f(p) + \sum_{i=p}^x [\zeta(i)>=p]f(i)$

  那么

    $f(p)(S'(\frac{i}{p})-S'(p-1) )= \sum_{j=p}^{\frac{i}{p}} [\zeta(i)>=p] f(i*p)$

  即此时我们给$S'(i)$删去了所含质因数均大于等于$p$的合数。故上式当处理到$\sqrt n$时是正确的。

  

  我们再考虑如何求出$a,b$数组。

  显然我们要从小到大枚举每个质数,再从大到小枚举每一个有用的$i$。然后考虑:

  1)  若$i>\sqrt n$那么其对应位置一定在$b$数组出现过。

  2)  若$\frac{i}{p}>sqrt n$那么其对应位置也必然在$b$中出现,这是由于$i$是由$\frac {n} {j}$得到的。

   那么$\frac{i}{p}$就等价于$\lfloor \frac{ \frac{n}{j} }{p} \rfloor= \frac {n} {jp}$显然$jp<=\sqrt n$ 那么其此时$\frac{i}{p}$一定在b中出现过。

  3) 若$i<=\sqrt n$ 那么其必然出现在$a$中,$\frac{i}{p}$同理。

  也就是说对于用每个$p$来更新$a,b$需要且仅需要$a,b$数组。

  考虑求$a,b$的时间复杂度约为:

  $ \sum_{i=2,i=\tau i} (2\sqrt n - i^2) $。

  这个东西,应该约为$\frac {2n^\frac{3}{4}} {3ln(\sqrt n)}$。考虑枚举第一部分$i$具有常数。这两部分应该是很接近的。

算法使用范围:

  假设我们可以将一个函数写成关于$p$的$k$阶多项式形式的话,我们就可以利用上面描述的筛法,在$k\frac{n^\frac{3}{4}}{lnn}$时间内得到答案。

======update======

  这个似乎就是min_25筛。

  上了SPOJ以后才发现……min_25可能就是Hiroaki Yamanouchi……