杜教筛

· · 个人记录

用处

杜教筛是在非线性时间内处理积性函数的前缀和

积性函数

积性函数：对于任意互质的整数 a,b 有 f(ab)=f(a)f(b) 则称 f(x) 为积性函数。

完全积性函数：对于任意整数 a,b 有 f(ab)=f(a)f(b), 则称f(x)为积性函数。

常见的积性函数：\varphi,\mu,\sigma,d

$ σ(n) $——约数和函数 常见的完全积性函数：$\epsilon=(n=1),I=1,id=n

狄利克雷卷积

设 f, g 是两个数论函数，它们的狄利克雷卷积卷积是：

(f*g)(n)= \sum_{d|n}f(d)g(\dfrac{n}{d})

性质：满足交换律，结合律

单位元：\epsilon （即 f*\epsilon=f）

结合狄利克雷卷积得到的几个性质：

  1. \mu$ ∗ $I = \epsilon $ , $ (\sum_{d|n}\mu(d)=1,n=1)
  2. \varphi * I = id$ , $(\sum_{d|n}\varphi(d)=n)
  3. \mu * id = \varphi$ , $ (\dfrac{\varphi(n)}{n}=\sum_{d|n} \dfrac{\mu(d)}{d})

杜教筛

\sum\limits_{i=1}^{n}(f*g)(i) = \sum\limits_{i=1}^{n}g(i)S(\left\lfloor\dfrac{n}{i}\right\rfloor)

可得出

g(1)S(n)=\sum \limits _{i=1}^{n} (g*f) (i) - \sum \limits _{i=2}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor)

所以现在如果可以找到一个合适的积性函数 g ，使得可以快速算出 \sum\limits_{i=1}^{n}(f*g)(i) 和 g 的前缀和，便可以用数论分块递归地求解。

模板

long long get_mu(int n)
{
    if(n<=maxn)
        return mu[n];
    if(Smu[n])
        return Smu[n];
    long long res=1ll;
    for(int l=2,r;l<=n;l=r+1){
        r=n/(n/l);
        res-=(r-l+1)*get_mu(n/l);
    }
    return Smu[n]=res;
}
long long get_phi(int n)
{
    if(n<=maxn)
        return phi[n];
    if(Sphi[n])
        return Sphi[n];
    long long res=1ll*n*(n+1)/2;
    for(int l=2,r;l<=n;l=r+1){
        r=n/(n/l);
        res-=(r-l+1)*get_phi(n/l);
    }
    return Sphi[n]=res;
}