积性函数的筛法

Recalling_Clouds

已于 2022-02-10 20:38:17 修改

阅读量239

点赞数

分类专栏：学习笔记文章标签：数学

于 2022-01-20 22:21:31 首次发布

本文链接：https://blog.csdn.net/PythonYX/article/details/122611397

版权

本文介绍了数论中积性函数的筛法，包括欧拉筛、杜教筛和Min_25筛等，这些方法能有效地计算积性函数的前缀和，特别是线性复杂度的欧拉筛适合处理所有积性函数。文章还探讨了如何针对不同积性函数特点进行优化，并提供了实际应用的代码示例。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

下面的所有知识均属数论范畴。

欧拉筛

可以做到 $O (n)$ 的线性复杂度！

可以筛所有的积性函数（即对于所有的 $\perp b$ 都满足 $f (a b) = f (a) * f (b)$ 的函数)。

举两个例子：

线性筛欧拉函数：

inline void Sieve()
{
   
    phi[1] = 1;
    for(register int i = 2; i <= MAXN; i++)	//MAXN表示值域
    {
   
        if(!NotPrime[i])	//是质数
        {
   
            phi[i] = i - 1;
            Prime[++len] = i;
        }
        for(register int j = 1; j <= len && i * Prime[j] <= MAXN; j++)
        {
   
            NotPrime[i * Prime[j]] = true;
            if(i % Prime[j] == 0)	//此时 Prime[j] 为 i 的最小质因子
			{
   
            	phi[i * Prime[j]] = phi[i] * prime[j];
				break;
            }
            phi[i * Prime[j]] = phi[i] * (Prime[j] - 1);
        }
    }
    return;
}

线性筛莫比乌斯函数：

inline void Sieve()
{
   
    miu[1] = 1;
    for(register int i = 2; i <= MAXN; i++)
    {
   
        if(!NotPrime[i])
        {
   
            miu[i] = -1;
            Prime[++len] = i;
        }
        for(register int j = 1; j <= len && i * Prime[j] <= MAXN; j++)
        {
   
            NotPrime[i * Prime[j]] = true;
            if(i % Prime[j] == 0) break;	//此时 miu 函数值为 0，可以直接跳过
            miu[i * Prime[j]] = -miu[i];
        }
    }
    return;
}

可以发现，每个数最多只会被自己的最小质因子筛到一次，所以时间复杂度是线性的 $O (n)$ 。

不过要注意，每个数被自己的最小质因子筛到时，对应的 i * Prime[j]仍然是需要计算函数值的！（当然 $\mu$ 函数此时就等于 $0$ ，可以直接跳过）

杜教筛

在非线性时间内求解积性函数的前缀和。

设现在我们要求的是 $f$ 的前缀和，即 $\sum_{i = 1} ^n f(i)$ 。

我们考虑把 $f$ 卷上一个 $g$ 的前缀和，即：
$\begin{aligned} S'(n) &= \sum_{i = 1}^n(f * g)(i) \\ &= \sum_{i = 1} ^n \sum_{d | i} f(d)g(\frac{i}{d}) \\ &=\sum_{d = 1}^n g(d) \sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor} f(i) \\ &=\sum_{d = 1}^ng(d)S(\lfloor\frac{n}{d}\rfloor) \end{aligned}$
然后再推导一下，发现：
$\sum_{d = 1}^ng(d)S(\lfloor\frac{n}{d}\rfloor) - \sum_{d = 2}^ng(d)S(\lfloor\frac{n}{d}\rfloor)$
即：
$\frac{\sum_{i = 1}^n(f * g)(i) - \sum_{d = 2}^ng(d)S(\lfloor\frac{n}{d}\rfloor)}{g(1)}$
所以，只要我们找到合适的 $g$ ，就能够快速求出 $S (n)$ 了。