杜教筛学习笔记

发布于 2018-08-17  308 次阅读


预备知识

杜教筛是一种能在比线性复杂度还优秀的复杂度中处理处积性函数的前缀和。

主要运用 Dircichlet 卷积来完成复杂度的化简。

定义

设 $ f(n) $ 为一个数论函数,$ S(n) = \Sigma_{i=1}^nf(i)$。

我们考虑再找到一个合适的数论函数 $g(i)$,使得

$$ \Sigma_{i=1}^n\Sigma_{d|i}f(d)g(\frac{i}{d}) = \Sigma_{i=1}^ng(i)S(\frac{n}{i}) \tag1$$

也就是

$$ g(1)S(n) = \Sigma_{i=1}^n(f*g)(i) - \Sigma_{i=2}^ng(i)S(\frac{n}{i}) \tag2$$

可以通过线性筛预处理前 $ O(n^{\frac{2}{3}}) $ 项,其他暴力递归算。复杂度为 $ O(n^{ \frac{2}{3}}) $。

例题

题目链接

题目描述

有 $ T $ 组询问,对于每组询问,给出一个数 $ n $,求 $$ \Sigma_{i=1}^n \mu(i) $$ 和 $$ \Sigma_{i=1}^n \phi(i) $$ 的值。

其中 $ n \leq 2^{31}-1,T \leq 10 $

解题报告

莫比乌斯函数 $ \mu $

$$ \Sigma_{i=1}^n\mu(i) \tag1$$

我们需要选取一个合适的函数,使得

$$ g(1)S(n) = \Sigma_{i=1}^n(f*g)(i) - \Sigma_{i=2}^ng(i)S(\frac{n}{i}) \tag2 $$

中 $ g $ 和 $ S $ 是容易快速处理的,这样就可以推出 $ f $。

显然,我们对于第一个式子选择常函数 $ f(x) = 1 $

$ (2) $ 式变形为:

$$ S(n)=\Sigma_{i=1}^n(\mu*1)(i) - \Sigma_{i=2}^n S(\lfloor\frac{n}{i}\rfloor) \tag3$$

注意性质 $ \mu * 1 = e $,整理得到

$$ S(n) = 1 - \Sigma_{i=2}^nS(\lfloor\frac{n}{i}\rfloor) \tag4$$

直接计算的复杂度为 $ O(n^{\frac{3}{4}}) $ ,但是可以考虑线性筛处理前 $ n^{\frac{2}{3}} $ 项,这样递推时间复杂度为:

$$ O(\int^{n^{\frac{1}{3}}}_0\sqrt{\frac{n}{x}}dx) = O(n^{\frac{2}{3}}) \tag1 $$

$ (1) $ 式结合线性筛部分,总复杂度为 $ O(n^{\frac{2}{3}}) $。

欧拉函数 $ \phi $

用和上题一样的方法,留给读者自己思考。

提示: 欧拉函数有性质 $ \phi * 1 = id $。

参考代码

#include 
#include 
#include 
#include 
#include 
#include 

#define LL long long
const int MAXN = 5e6 + 10;
const int POIN = 5e6;

LL T,cnt,mu[MAXN],phi[MAXN];
int prime[MAXN];
bool p[MAXN];

void pre(){
    mu[1] = phi[1] = 1;
    for(int i = 2;i <= POIN;i++){
        if(!p[i]){
            prime[++cnt] = i;
            mu[i] = -1;
            phi[i] = i-1;
        }
        for(int j = 1;j <= cnt && i * prime[j] <= POIN;j++){
            p[i*prime[j]] = 1;
            if(!(i % prime[j])){
                phi[i*prime[j]] = phi[i] * prime[j];
                // mu[i*prime[j]] = 0;
                break;
            }
            mu[i*prime[j]] = -mu[i];
            phi[i*prime[j]] = phi[i] * phi[prime[j]];
        }
    }
    for(int i = 1;i <= POIN;i++){
        mu[i] += mu[i-1];
        phi[i] += phi[i-1];
    }
}

std::map mmu,mphi;
LL query1(LL x)
{
    if(x<=5e6)return phi[x];
    if(mphi.find(x) != mphi.end())return mphi[x];
    LL tmp=x*(x+1)/2;LL i,j;
    for(i=2;i<=x;i=j+1)
    {
        j=x/(x/i);
        tmp-=(j-i+1)*query1(x/i);
    }
    return mphi[x]=tmp;
}

LL query2(LL n){
    if(n <= POIN)
        return mu[n];
    if(mmu.find(n) != mmu.end()) return mmu[n];
    LL t = 1;
    LL i,last;
    for(i = 2;i <= n;i = last + 1){
        last = n/(n/i);
        t -= (last-i+1)*query2(n/i);
    }
    return mmu[n] = t;
}

int main(){
    LL n;int T;
    scanf("%d",&T);
    pre();
    while(T--){
        scanf("%d",&n);
        printf("%lld %lld\n",query1(n),query2(n));
    }
    return 0;
}


一个OIer。