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

· · 算法·理论

更好的观感体验。

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

筛法求因数和

给定 n，求 1\text{\textasciitilde}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 $$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 $$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)\text{\textasciitilde}\mu(n)

前置知识补充

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

n=\prod_{i=1}^s p_i^{a_i} \mu(n)=\begin{cases}1&n=1\\0&n\texttt{含有相同质因子}\\(-1)^s&s\texttt{为}n\texttt{的不同质因子个数}\end{cases}

筛法实现

定义数组 $mu$，$mu_i=\mu(i)$，定义 $m=i\times p_j
  1. i\mod p_j=0
  2. i\mod p_j\not=0 $$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];
    }
}
}

    总结

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

筛法可以求：

还有，欢迎来到我的博客玩哦！