筛法求因数和、莫比乌斯函数

更洛谷的观感体验。

好吧，也是不鸽了，上篇文章的续集来了。

筛法求因数和

给定 $n$，求 $1$ ~ $n$ 的因数和。

前置芝士补充

根据唯一分解定理，一个数 $n$ 为：

$$n=\prod_{i=1}^s p_i^{a_i}$$

一个质数 $p_i^{a_i}$ 的因数有 $p_i^0,p_i^1,p_i^2,…,p_i{a_i}$，共有 $a_i+1$ 个因数，质数 $p_i^{a_i}$ 的因数和为：

$$f(p_i^{a_i})=\sum^{a_i}_{j=0}p_i^j$$

因为 $n$ 有多个这个因数，所以 $n$ 的因数和为：

$$f(n)=\prod^s_{i=1}\sum^{a_i}_{j = 0}p_i^j$$

筛法实现

定义两个数组 $g,f$，分别记录最小质因子不同次幂的和和约束和。

分为两种情况。

1. $i\mod p_j=0$
   $p_j$ 是 $i$ 的最小质因子，设 $i$ 中 $p_j$ 的指数为 $a_j$，则：

   $$g_i=\sum^{a_j}_{k=0}p_j^k$$

   标记的数 $m=p_j\times i$ 中的指数为 $a_j+1$，则：

   $$g_m=\sum^{a_j+1}_{k=0}p_j^k$$

   $$f_m=\frac{f_i\times g_m}{g_i}$$

2. $i\mod p_j\not=0$
   $i$ 不包含质因子 $p_j$：

   $$g_m=1+p_j$$

   其中的 $1$ 是 $p_j^0$。

   $$f_m=g_m\times f_i$$

还有，如果 $i$ 为质数，则：

$$g_i=f_i=1+i$$

$\texttt{Code}$

int p[N], cnt, g[N], f[N];
void get_f(int n)
{
	g[1] = f[1] = 1;
	for(int i = 2; i <= n; i++)
	{
		if(!vis[i])
			p[++cnt] = i, g[i] = f[i] = i + 1;
		for(int j = 1; j <= n; j++)
		{
			int m = p[j] * i;
			vis[m] = true;
			if(i % p[j] == 0)
			{
				g[m] = g[i] * p[j] + 1;
				f[m] = f[i] / g[i] * g[m];
				break;
			}
			g[m] = p[j] + 1;
			f[m] = f[i] * g[m];
		}
	}
}

筛法求莫比乌斯函数

给定 $n$，求 $\mu(1)$ ~ $\mu(n)$

前置知识补充

根据唯一分解定理，一个数 $n$ 为：

$$n=\prod_{i=1}^s p_i^{a_i}$$

如果 $n = 1$，$\mu(n)=1$。
如果 $n$ 含有相同质因子，$\mu(n)=0$。
否则 $\mu(n)=(-1)^s$，$s$ 为 $n$ 的不同质因子个数。

筛法实现

$p$ 为质数则 $\mu(p)=-1$。
定义数组 $mu$，$mu_i=\mu(i)$，定义 $m=i\times p_j$

1. $i\mod p_j=0$
   $i$ 包含质因子 $p_j$，则 $mu_m=0$（因为第 $2$ 条规则）。
2. $i\mod p_j\not=0$
   $m$ 比 $i$ 多一个质因子 $p_j$，则：

   $$mu_m=-mu_i$$

$\texttt{Code}$

int p[N], cnt, mu[N];
bool vis[N];
void get_mu(int n)
{
	mu[1] = true;
	for(int i = 2; i <= n; i++)
	{
		if(!vis[i])
			p[++cnt] = i, mu[i] = -1;
		for(int j = 1; p[j] * i <= n; j++)  
		{
			int m = p[j] * i;
			vis[m] = true;
			if(i % p[j] == 0)
			{
				mu[m] = 0;
				break;
			}
			else
				mu[m] = -mu[i];
		}
	}
}

总结

这次我们学习了筛法求因数和、莫比乌斯函数。

筛法可以求：

• 质数
• 欧拉函数（$\varphi$）
• 因数个数
• 因数和
• 莫比乌斯函数（$\mu$）