亚线性筛之一

杜教筛

前置知识

积性函数

前言

首先先看一下积性函数吧，积性函数就是在对于所有的互质的 $a$ 和 $b$ ，总有 $f(ab) = f(a)f(b)$ ， 则 $f(x)$ 为积性函数。

比较常见的主要有：

$$d(x)= \sum_{i \mid n} 1 \\ \sigma (x) = \sum_{i \mid n} i \\ \varphi (x) = \sum_{i=1}^x 1 [gcd(x,i)=1] \\ \mu (x) = \left\{ \begin{aligned} &1 &x=1 \\ &(-1)^k &\prod_{i=1}^k q_i=1 \\ &0&\max\left\{ q_i \right\} > 1 \end{aligned} \right. \\ \epsilon (x) = [x=1]$$

积性函数有以下性质：
若 $f(x),g(x)$为积性函数，则，

$$h(x) = f(x^p) \\ h(x) = f^p(x) \\ h(x) = f(x)g(x) \\ h(x) = \sum_{d \mid x} f(d)g(\frac{x}{d})$$

中的$h(x)$也为积性函数。

杜教筛主要是用来求像这些积性函数的前缀和。

正文

对于求一个数论函数的前缀和，杜教筛可以在低于线性时间的复杂度内求解。

对于数论函数 $f$ ， 要求计算 $S(n) = \sum_{i=1}^n f(i)$ 。

首先构造一个 $S(n)$ 关于$S(\left\lfloor\frac{n}{i}\right\rfloor)$ 的递推式

对于任意一个数论函数 $g$ ，必须满足

$$\sum_{i=1}^n \sum_{d \mid i}g(d)f(\frac{i}{d})= \sum_{i=1}^ng(i)S(\left\lfloor\frac{n}{i}\right\rfloor) \iff \sum_{i=1}^n(f \ast g)(i) = \sum_{i=1}^ng(i)S(\left\lfloor\frac{n}{i}\right\rfloor)$$

简单的证明：

$$\sum_{i=1}^n \sum_{d \mid i}g(d)f(\frac{i}{d})\\ = \sum_{i=1}^n\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor} g(i)f(j)\\ = \sum_{i=1}^ng(i)\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor} f(j)\\ = \sum_{i=1}^ng(i)S(\left\lfloor\frac{n}{i}\right\rfloor) \\$$

求出递推式

$$g(1)S(n)=\sum_{i=1}^n(f \ast g)(i)-\sum_{i=2}^ng(i)S(\left\lfloor\frac{n}{i}\right\rfloor)$$

可以用数论分块对后半部分快速求出结果。

问题

• 题目：求 ：

$$S_1(n)=\sum_{i=1}^n \mu(i)\\ S_2(n)=\sum_{i=1}^n \varphi(i)$$

第一部分求莫比乌斯函数前缀和

$$\because \epsilon =\mu \ast 1 \\ \therefore \epsilon = \sum_{d \mid n}\mu (d) \\ S_1(n) = \sum_{i=1}^n \epsilon(i) -\sum_{i=2}^nS_1(\left\lfloor\frac{n}{i}\right\rfloor) \\ = 1-\sum_{i=2}^nS_1(\left\lfloor\frac{n}{i}\right\rfloor)$$

直接整除分块

第二部分求欧拉函数前缀和

$$\because \varphi \ast 1 =ID \\ \therefore \sum_{i=1}^n (\varphi \ast 1)(i)=\sum_{i=1}^n 1 \cdot S_2(\left\lfloor\frac{n}{i}\right\rfloor) \\ \sum_{i=1}^n ID(i)= \sum_{i=1}^n 1 \cdot S_2(\left\lfloor\frac{n}{i}\right\rfloor) \\ \frac{1}{2}n(n+1) = \sum_{i=1}^nS_2(\left\lfloor\frac{n}{i}\right\rfloor) \\ S_2(n)=\frac{1}{2}n(n+1)-\sum_{i=2}^nS_2(\left\lfloor\frac{n}{i}\right\rfloor) \\$$

时间复杂度$O(n ^{\frac{2}{3}})$

code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e6+10;
int T,cnt,n;
ll mu[maxn],prime[maxn],S1[maxn],S2[maxn];
bool vis[maxn];
map<ll,ll> eit;
void Mu()
{
    mu[1]=1;
    for(int i=2;i<=2e6;i++)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&prime[j]*i<=2e6;j++)
        {
            vis[prime[j]*i]=true;
            if(i%prime[j]==0)
            {
                mu[prime[j]*i]=0;
                break;
            }
            mu[prime[j]*i]=-mu[i];
        }
    }
    for(int i=1;i<=2e6;i++)
        S1[i]=S1[i-1]+mu[i];
}
ll S_mu(ll x)
{
    if(x<=2e6)return S1[x];
    if(eit[x])return eit[x];
    ll res=1;
    for(ll l=2,r;l<=x;l=r+1)
    {
        r=x/(x/l);
        res-=S_mu(x/l)*(r-l+1);
    }
    return eit[x]=res;
}
ll S_phi(ll x)
{
    ll res=0;
    for(ll l=1,r;l<=x;l=r+1)
    {
        r=x/(x/l);
        res+=(S_mu(r)-S_mu(l-1))*(x/l)*(x/l);
    }
    return (res-1)/2+1;
}
int main()
{
    Mu();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld",&n);
        printf("%lld %lld\n",S_phi(n),S_mu(n));
    }
    return 0;
}

对于一些筛法的小技巧：

对于比较大的数据时，筛法在筛前半段时花费的时间显然是比较长的，这时我们可以直接线性筛一遍先记录下来，在求后半段时就可以省下大部分时间，称为根号分治。