积性函数筛法（1）_算法

积性函数筛法（1）

本文来介绍一些基础性概念，为后文服务。

可能适合于已经会一点点下述内容的人来看，可能会增进你的理解。

• 积性函数
  • 概念
  • $\rm Dirichlet$ 卷积
  • 常见积性函数
• 线性筛
  • 线性筛素数/求普通积性函数
  • 线性筛 $\rm Dirichlet$ 卷积/任意积性函数
• 整除分块
  • 普通整除分块
  • 多限制整除分块
  • 平方整除分块
  • 整除分块的常数优化：$\rm Dirichlet$ 双曲线法
• 莫比乌斯反演
  • 概念
  • 欧拉反演
  • 偏序集上的莫比乌斯反演
• 例题

积性函数

概念

我们把 $f:\mathbb N^+\to \mathbb R$ 的函数 $f$ 称为 数论函数，其中 $\mathbb R$ 为交换环，应用中的数论函数一般定义域为 $\mathbb N^+$，值域为 $\mathbb Z$。

满足 $\forall a,b\in\mathbb N^+,f(ab)=f(a)f(b)$ 的数论函数 $f$ 我们称为 完全积性函数，不难看出 $f(1)=1$。

满足 $\forall a,b\in\mathbb N^+,a\perp b,f(ab)=f(a)f(b)$ 的数论函数 $f$ 称为 积性函数，同样的，$f(1)=1$。

分析一下可以发现，完全积性函数仅需每个质数处的值即可确定整个函数，考虑唯一分解定理 $n=\prod_ip_i^{c_i}$，则 $f(n)=\prod_if(p_i)^{c_i}$。

相似的，积性函数的被质数和质数幂处的值决定，$f(n)=\prod_if(p_i^{c_i})$。

$\rm Dirichlet$ 卷积

定义满足 $\forall n\in\mathbb N^+,h(n)=\sum_{d|n}f(d)g(\frac n d)$ 的数论函数 $h$ 为数论函数 $f,g$ 的 $\rm Dirichlet$ 卷积，记作 $h=f*g$。

为了避免记号混乱，本文使用 $f^c$ 表示 $c$ 个 $f$ 相乘（就是对应位置相乘），$f^{c*}$ 表示 $f$ 做了 $c$ 次 $\rm Dirichlet$ 卷积，例如 $f^{0*}=\epsilon,f^{-*}$ 为 $f$ 的 $\rm Dirichlet$ 逆元。

常见积性函数

最基础也是最重要的，单位元 $\epsilon$，$\epsilon(n)=[n=1]$，任意函数 $f*\epsilon=f$。

接着我们可以定义 $I(n)=1,id(n)=n,id^c(n)=n^c$。

然后我们自然好奇 $I^{-*}$，我们定义其为 $\mu$，满足：

$$n=\prod_{i}p_i^{c_i},\mu(n)=\begin{cases}0,&\max_ic_i\ge 2\\(-1)^{\sum_ic_i},&\max_ic_i\le 1\end{cases}$$

$\mu$ 作为 $I^{-*}$，在许多位置起到的作用其实是容斥系数，如果每个因数都会把该值对应合法方案统计一次导致统计重复，那么将 $f_x\gets\sum_{d|x}f_d$ 变为 $f_x\gets \sum_{d|x}\mu(d)f_d$ 即可统计到真正的答案。

顺便还有 $id*\mu$，我们定义其为 $\varphi$，满足 $\varphi(n)=\sum_{i\le n}[i\perp n]$。

自然我们就有了如下几个式子：

$id*\mu=\varphi,I*\varphi=id,\mu*I=\epsilon$。

记忆法则就是 $I$ 和 $\mu$ 是互为 $\rm Dirichlet$ 逆元的。

还有 $\sigma_c(n)=\sum_{i\le n}[i\perp n]i^c,d=\sigma_0$ 即为约数个数，$\sigma=\sigma_1$ 为约数和。

在估计 $d(n)$ 的量级时一般取 $\cal O(n^{1/3})$。

线性筛

线性筛素数/求普通积性函数

普通的埃筛之所以不能做到严格 $\mathcal O(n)$，还是因为每个数被筛掉了多次，那么我们令每个数在其最小质因子处被筛掉，就做到了严格线性。

vec<int> P;bitset<N> is;
void init(int n) {
    F(i,2,n) {
        if(!is[i]) P+=i;
        for(int p:P) if(i*p<=n) {
            is[i*p]=1;
            if(i%p==0) break;
        } else break;
    }
}

若 $i\bmod p=0$，则说明 $i$ 中最小质因子已经与 $p$ 相等了，继续枚举 $p$ 就不是在 $i\times p$ 的最小质因子处被筛掉了，所以需要及时 break。

线性筛也可以求普通（常见）积性函数，这里略过，大多利用了其各自的特殊性质。

线性筛 $\rm Dirichlet$ 卷积/任意积性函数

前文说过，积性函数由质数及质数幂处的值决定，所以我们利用这个性质来求解任意可以快速求出“质数及质数幂处的值”的积性函数。

vec<int> P;int low[N],f[N];
void init(int n) {
    f[1]=low[1]=1;
    F(i,2,n) {
        if(!low[i]) {
            P+=i;low[i]=i;
            for(ll x=i;x<=n;x*=i) {
                //calc f[x]
            }
        }
        for(int p:P) if(i*p<=n) {
            is[i*p]=1;
            if(i%p==0) {
                low[i*p]=low[i]*p;
                f[i*p]=f[i/low[i]]*f[p*low[i]];break;
            } f[i*p]=f[i]*f[p];low[i*p]=p;
        } else break;
    }
}

只需单独记录 $\text{low}_i$ 表示 $i$ 的最小质因子幂即可。

线性筛两个函数的 $\rm Dirichlet$ 卷积也是同理，因为我们可以 $\mathcal O(k)$ 求出 $f(p^k)$ 的值，一个质数的 $\mathcal O(\log V)$ 个幂做一个等差数列求和虽然是 $\mathcal O(\log^2 V)$ 的，但由于质数的 $\log$ 底数较大，实际分析中通常可以分析到常数的级别，此处不展开论述，讲解洲阁筛时仍会涉及到类似的分析。