线性筛与积性函数

线性筛是一种数论筛法，可以筛出一定范围内的质数或任意积性函数的值。

其中”线性“的含义为 每个数字只被其最小的质因数筛出 ，并非时间复杂度。

假设求积性函数 $f(x)$ 的质数幂 $f(p^k)$ 复杂度为 $t$，则最终复杂度为 $ \mathcal O(n+\frac{n}{\ln n}\times t)$ 。

数论函数

定义域为正整数集 $\mathbb N^+$，陪域为复数集 $\mathbb C$ 的函数。

常见的数论函数可视为，定义域为正整数，值域为整数的函数。

积性函数

对于一个数论函数 $f$ ， $\forall\ a\ \bot\ b,\ f(ab) = f(a)\times f(b)$，则称 $f$ 为积性函数。

若 $n$ 的标准分解为 $n = p_1^{k_1}\times p_2^{k_2}\times …\times p_m^{k_m}\ (p_1<p_2<…<p_m)$ ，则

$f(n)=\prod_{i=1}^m f(p_i^{k_i})$

这也是线性筛的基础，即积性函数的基本性质之一就是可被线性筛。

完全积性函数

对于一个数论函数 $f$ ， $\forall\ a,b\in \mathbb N^+ ,\ f(ab) = f(a)\times f(b)$，则称 $f$ 为完全积性函数。

线性筛

求 $f(n)$ 的值时，考虑其标准分解

$n = p_1^{k_1}\times p_2^{k_2}\times ...\times p_m^{k_m}\ (p_1<p_2<...<p_m)$

对标准分解的最小质因数的指数 $k_1$ 的情况讨论。

$n$ 是素数 $p_1$，即 $k_1=m=1$
$n=p_1\times i$，其中 $i$ 是任意正整数，且 $k_1=1$，即 $p_1\nmid i$
$n=p_1\times i$，其中 $i$ 是任意正整数，且 $k_1>1$，即 $p_1\mid i$

下面对三类情况分别进行处理：

$n$ 是素数 $p_1$，即 $k_1=m=1$

往往可以利用数论函数的定义快速求出。
$n=p_1\times i$，其中 $i$ 是任意正整数，且 $k_1=1$，即 $p_1\nmid i$

利用积性函数的定义，由于 $p_1\bot i$，有 $f(n) = f(p_1) \times f(i)$

由于 $p_1<n,\ i<n$，$f(p_1)$ 和 $f(i)$ 在此前都已求出。
$n=p_1\times i$，其中 $i$ 是任意正整数，且 $k_1>1$，即 $p_1\mid i$

将 $n$ 重新表示为 $n=p_1^{k_1}\times j$ 的形式，此时 $p_1^{k_1}\bot j$，有$f(n)=f(p_1^{k_1})\times f(j)$

由于 $p_1^{k_1}<n, j<n$，$f(p_1^{k_1})$ 和 $f(j)$ 在此前都已求出。

现在只需要解决如何快速求出 $n$ 对应的 $p_1^{k_1}$ 和 $k_1$ 的值。

不妨设 $g(n)=p_1^{k_1},\ k(n)=k_1$，这两个函数虽然不是积性的，但依然可以按照上述思路讨论。

$n$ 与 $p_1$ 关系	$g(n)$	$k(n)$
$n$ 是素数 $p_1$	$p_1$	$1$
$n=p_1\times i$，且 $p_1\nmid i$	$p$	$1$
$n=p_1\times i$，且 $p_1\mid i$	$g(i)\times p_1$	$k(i)+1$

因此我们可以在线性筛的同时求出 $g(n)$ 和 $k(n)$，复杂度不变。

应用

下面展示一些积性函数的线性筛法。

对应函数的积性证明参考这里，本篇不再证明。

下面提到的 $n,m,i,j,p,k$ 的定义与上述内容相同。

线性筛质数

本质上是筛 最小质因数 $d_{min}(n)=p_1$，若 $d_{min}(n)=n$ 则这个数为质数。

这个函数也不是积性函数，但是对于由当前质数 $p_i$ 筛掉的任意合数 $n$，都有 $d_{min}(n)=p_i$

Sample-Code

for (int i = 2; i <= n; ++i) {
    if (!mindiv[i]) prime[++tot] = mindiv[i] = i;
    for (int j = 1; j <= tot; ++j) {
        if (prime[j] > mindiv[i] || prime[j] * i > n) break;
    	mindiv[prime[j] * i] = prime[j];
    }
}

线性筛 $\mu$

莫比乌斯函数 $\mu$ 是积性函数，定义为

$\mu(n)= \begin{cases} 1 \qquad & n=1 \\ (-1)^k \qquad & n=\Pi_{i=1}^{k} p_i \\ 0 \qquad & \text{otherwise} \end{cases}$

易得 $\mu(p_i^k)=0(k>1)$，直接按条件分讨就可以。

$n$ 与 $p_1$ 关系	$\mu(n)$
$n$ 是素数 $p_1$	$-1$
$n=p_1\times i$，且 $p_1\nmid i$	$\mu(p_1)\times \mu(i)=-\mu(i)$
$n=p_1\times i$，且 $p_1\mid i$	$\mu(p_1^{k_1})\times\mu(j)=0$

Sample-Code

mu[1] = 1;
for (int i = 2; i <= n; ++i) {
    if (!mindiv[i]) prime[++tot] = mindiv[i] = i, mu[i] = -1;
    for (int j = 1; j <= tot; ++j) {
        if (prime[j] > mindiv[i] || prime[j] * i > n) break;
    	mindiv[prime[j] * i] = prime[j];
        mu[prime[j] * i] = (i % prime[j]) ? -mu[i] : 0;
    }
}

线性筛 $\varphi$

欧拉函数 $\varphi$ 是积性函数，定义为

$\varphi(n)=\sum_{i=1}^n[i\bot n]$

同时有 $\varphi$ 计算公式（证明见这里)

$\varphi(n)=n\prod_{i=1}^m \frac{p_i-1}{p_i}$

由计算公式知，第三类情况

$\varphi(n)=\varphi(p_1^k)\times\varphi(j)=(p_1-1)\times p_1^{k-1}\times \varphi(j)\\ \varphi(i)=\varphi(p_1^{k_1-1})\times \varphi(j)=(p_1-1)\times p_1^{k_1-2}\times \varphi(j)$

因此有

$\varphi(n)=\varphi(i)\times p_1$

$n$ 与 $p_1$ 关系	$\varphi(n)$
$n$ 是素数 $p_1$	$n-1$
$n=p_1\times i$，且 $p_1\nmid i$	$\varphi(p_1)\times \varphi(i)=(p_1-1)\times \varphi(i)$
$n=p_1\times i$，且 $p_1\mid i$	$\varphi(p_1^k)\times\varphi(j)=p_1\times \varphi(i)$

Sample-Code

phi[1] = 1;
for (int i = 2; i <= n; ++i) {
    if (!phi[i]) prime[++tot] = i, phi[i] = i - 1;
    for (int j = 1; j <= tot; ++j) {
        if (prime[j] > mindiv[i] || prime[j] * i > n) break;
    	phi[prime[j] * i] = phi[i] * ((i % prime[j]) ? prime[j] - 1 : prime[j]);
    }
}

关于 $\sigma_k$

约束幂和函数 $\sigma_k$ 是积性函数，定义为

$\sigma_k(n)=\sum_{d|n}d^k$

也就是说，$\sigma_k$ 是一个函数族，代表 $n$ 的约数的 $k$ 次幂和。

下面我们从简到难介绍 $\sigma_k$ 的求法。

线性筛 $\tau$

约数个数函数 $\tau=\sigma_0$ 是积性函数，即约束的 $0$ 次幂和，定义为

$\tau(n)=\sigma_0(n)=\sum [d | n]$

利用多集合的计数思路，对于 $n$ 的标准分解，有

$\tau(n)=\sigma_0(n)=\prod_{i=1}^m (k_i+1)$

同样直接分类讨论即可，但注意维护 $g(n)$ 和计算 $\tau(p^k)$ 的位置。

$n$ 与 $p_1$ 关系	$\tau(n)$
$n$ 是素数 $p_1$	$2$
$n=p_1\times i$，且 $p_1\nmid i$	$\tau(p_1)\times \tau(i)=2\tau(i)$
$n=p_1\times i$，且 $p_1\mid i$	$\tau(p_1^k)\times\tau(j)$

Sample-Code

g[1] = tau[1] = 1;
for (int i = 2; i <= n; ++i) {
    if (!mindiv[i]) {
       	g[i] = i;
        tau[i] = 2;
        prime[++tot] = mindiv[i] = i;
    }
    for (int j = 1, temp; j <= tot; ++j) {
        temp = prime[j] * i;
        if (prime[j] > mindiv[i] || temp > n) break;
    	if (prime[j] == mindiv[i]) {
            g[temp] = g[i] * prime[j];
            if (g[temp] == temp) tau[temp] = tau[g[i]] + 1;
            else tau[temp] = tau[g[temp]] * tau[i / g[i]];
            continue;
        }
        g[temp] = prime[j];
        mindiv[temp] = prime[j];
        tau[temp] = 2 * tau[i];
    }
}

线性筛 $\sigma$

约数和函数 $\sigma=\sigma_1$ 是积性函数，即约束的 $1$ 次幂和，定义为

$\sigma(n)=\sigma_1(n)=\sum_{d|n} d$

利用多集合的计数思路，对于 $n$ 的标准分解，有

$\sigma(n)=\sigma_1(n)=\prod_{i=1}^m \sum_{j=0}^{k_i} p_i^j$

同样直接分类讨论即可，注意维护 $g(n),k(n)$ 和计算 $\sigma(p^k)$ 的位置。

由于计算 $\sigma(p^k)$ 单次复杂度为 $O(\log k)$，总复杂度依然保持线性。

$n$ 与 $p_1$ 关系	$\sigma(n)$
$n$ 是素数 $p_1$	$p_1+1$
$n=p_1\times i$，且 $p_1\nmid i$	$\sigma(p_1)\times \sigma(i)=(p_1+1)\times \sigma(i)$
$n=p_1\times i$，且 $p_1\mid i$	$\sigma(p_1^k)\times\sigma(j)$

Sample-Code

g[1] = k[1] = sigma[1] = 1;
for (int i = 2; i <= n; ++i) {
    if (!mindiv[i]) {
       	g[i] = i;
        k[i] = 1;
        sigma[i] = i + 1;
        prime[++tot] = mindiv[i] = i;
    }
    for (int j = 1, temp; j <= tot; ++j) {
        temp = prime[j] * i;
        if (prime[j] > mindiv[i] || temp > n) break;
    	if (prime[j] == mindiv[i]) {
            k[temp] = k[i] + 1;
            g[temp] = g[i] * prime[j];
            if (g[temp] == temp) sigma[temp] = sigma[g[i]] + fpow(prime[j], k[i]);
            else sigma[temp] = sigma[g[temp]] * sigma[i / g[i]];
            continue;
        }
        g[temp] = prime[j];
        k[temp] = 1;
        mindiv[temp] = prime[j];
        sigma[temp] = (prime[j] + 1) * sigma[i];
    }
}

线性筛 $\sigma_k$

约数幂和函数 $\sigma_k$ 是积性函数，即约束的 $k$ 次幂和，定义为

$\sigma_k(n)=\sum_{d|n} d^k$

为避免重复，用大写 $K$ 表示所求幂次。

同样直接分类讨论即可，注意维护 $g(n),k(n)$ 和计算 $\sigma_k(p^k)$ 的位置。

此时计算 $\sigma_k(p^k)$ 单次复杂度为 $\mathcal O(\log (k\times K))$，总复杂度不再保持线性。

$n$ 与 $p_1$ 关系	$\sigma_k(n)$
$n$ 是素数 $p_1$	$p_1^{K}+1$
$n=p_1\times i$，且 $p_1\nmid i$	$\sigma(p_1)\times \sigma(i)$
$n=p_1\times i$，且 $p_1\mid i$	$\sigma(p_1^k)\times\sigma(j)$

Sample-Code

g[1] = k[1] = sigma[1] = 1;
for (int i = 2; i <= n; ++i) {
    if (!mindiv[i]) {
       	g[i] = i;
        k[i] = 1;
        sigma[i] = fpow(i, K) + 1;
        prime[++tot] = mindiv[i] = i;
    }
    for (int j = 1, temp; j <= tot; ++j) {
        temp = prime[j] * i;
        if (prime[j] > mindiv[i] || temp > n) break;
    	if (prime[j] == mindiv[i]) {
            k[temp] = k[i] + 1;
            g[temp] = g[i] * prime[j];
            if (g[temp] == temp) sigma[temp] = sigma[g[i]] + fpow(prime[j], k[i] * K);
            else sigma[temp] = sigma[g[temp]] * sigma[i / g[i]];
            continue;
        }
        g[temp] = prime[j];
        k[temp] = 1;
        mindiv[temp] = prime[j];
        sigma[temp] = sigma[prime[j]] * sigma[i];
    }
}

优化

当 $K$ 很大的时候显然会超时，例如计算 $n=K=10^7$ 时，可以考虑打表。

找到 $p_i,k_i$ 可能的最大值，得到 $p\le 4\times 10^3,k_i\le 25$，直接记忆化省掉快速幂。

Sample-Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7 + 10, p = 1000000007;

// c[N] 即文中 k[N]
int n, k, pri[N], tot, c[N], mn[N], g[N];

bool vis[N];

ll f[N], ans;

int fpow(int a, ll b) {
	int r = 1;
	for( ; b ; b >>= 1, a = (ll) a * a % p) if(b & 1) r = (ll) r * a % p;
	return r;
}

int val[4000][25];

inline int F(int mn, int c) {
	if(val[mn][c] != -1) return val[mn][c];
	int r = 0;
	for(int j = 0 ; j <= c ; ++ j) r = ((ll) r + fpow(mn, (ll) j * k)) % p;
	return val[mn][c] = r;
}

int main() {
	memset(val, -1, sizeof val);
	scanf("%d%d", &n, &k);
	ans = f[1] = 1;
	for(int i = 2 ; i <= n ; ++ i) {
		if(!vis[i]) pri[++ tot] = i, f[i] = 1 + fpow(i, k), g[i] = i, c[i] = 1, mn[i] = i;
		for(int j = 1 ; j <= tot && (ll) i * pri[j] <= n ; ++ j) {
			int x = i * pri[j];
			vis[x] = 1;
			if(i % pri[j] == 0) {
				f[x] = f[i / g[i]] * F(mn[i], c[i] + 1) % p;
				g[x] = g[i] * pri[j];
				c[x] = c[i] + 1;
				mn[x] = pri[j];
				break;
			} else f[x] = f[i] * f[pri[j]] % p, g[x] = pri[j], c[x] = 1, mn[x] = pri[j];
		}
		ans = (ans + f[i]) % p;
	}
	printf("%lld\n", ans);
}

例题

对于一些未定义积性函数，线性筛的应用。

[2018 南京网络预赛] Sum

定义 $f(x)$ 为满足以下条件的有序二元组 $(a,b)$ 的方案数

$x = a\times b$
$a$ 和 $b$ 均无平方因子 ( $\mu(a)\neq 0,\mu(b)\neq 0$ )

求 $\sum_{i=1}^n f(i)$，数据范围 $n\le 2\times 10^7$

Solution

显然 $f(x)=\sum_{d|x} abs(\mu(d)\mu(\frac nd))$，是积性函数（相当于是重定义让 $\mu\ge 0$， $\mu*\mu$ ）。

$n$ 与 $p_1$ 关系	$f(n)$
$n$ 是素数 $p_1$	$2$
$n=p_1\times i$，且 $p_1\nmid i$	$f(p_1)\times f(i)=2f(i)$

对于 $n=p_1\times i$，且 $p_1\mid i$ 的情况，讨论：

若 $p_1 | \frac i{p_1}$ 即 $p_1 | \frac{n}{p_1^2}$ 时， $n$ 中 $p_1$ 的指数至少为 $3$ ，无论如何划分 $(a,b)$，都有一个 $\mu = 0$ ， $f(n) = 0$
否则 $p_1$ 的指数为 $2$ ，产生贡献必须把 $p_1$ 分给 $a$ 和 $b$ 各一个，即方案数 $f(n) = f(\frac{n}{p_1^2})$

#include<bits/stdc++.h>
#define N 20000007ll
using namespace std;

inline int rd() {
  int x = 0;
  char c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) {
    x = x * 10 + (c ^ 48);
    c = getchar();
  }
  return x;
}

bool vis[N];

int tot, f[N], prm[N];

inline void init() {
  f[1] = 1;
  for (int i = 2; i < N; ++i) {
    if (!vis[i]) prm[++tot] = i, f[i] = 2;
    for (int j = 1; j <= tot; ++j) {
       if (1ll * i * prm[j] >= N) break;
       vis[i * prm[j]] = 1;
       if (i % prm[j] == 0) {
         f[i * prm[j]] = ((i / prm[j]) % prm[j]) ? f[i / prm[j]] : 0;
         break;
       }
       f[i * prm[j]] = f[i] << 1;
    }
  }
  for (int i = 1; i < N; ++i) f[i] += f[i - 1];
}

int main() {
  init();
  int t = rd();
  while (t--) printf("%d\n", f[rd()]);
  return 0;
}

(还有一种做法即 $f=\mu^2 *\mu^2$ ，反演即可，查询单次 $\mathcal O(\sqrt n)$ ，参考这里)