定义

若函数 \(f(n)\) 满足 \(f(1)=1\) 且 \(\forall x,y \in {\Bbb{N}}_{+},{\rm{gcd}}(x,y)=1\) 都有 \(f(xy)=f(x)f(y)\) ，则 \(f\) 为积性函数。

若函数 \(f(n)\) 满足 \(f(1)=1\) 且 \(\forall x,y \in {\Bbb{N}}_{+}\) 都有 \(f(xy)=f(x)f(y)\) ，则 \(f\) 为完全积性函数。

性质

比较重要的有：若 \(f,g\) 为积性函数，则满足

\[h(n)=\sum_{d|n}f(d)g(\frac{n}{d}) \]

的函数 \(h\) 也为积性函数。

函数 \(h\) 称作 \(f,g\) 的Dirichlet卷积，记作 \(f*g\) 。

例子

单位函数

\[\epsilon(n)=[n=1] \]

有：

\[\epsilon=\mu*{\rm{I}} \iff \epsilon(n)=\sum_{d|n}\mu(d) \]

这个式子尤其常用。

任何函数卷 \(\epsilon\) 都为其本身。

恒等函数

\[{\rm{id}}_k(n)=n^k \]

一般用 \({\rm{id}}\) 表示 \({\rm{id}}_1\) 。

常数函数

\[{\rm{I}}(n)=1 \]

在杜教筛中有用到。

除数函数

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

一般 \(\sigma_0\) 记作 \({\rm{d}}\) ，\(\sigma_1\) 记作 \(\sigma\) 。

对于 \(\sigma\) ，有：

\[\sigma={\rm{id}}*{\rm{I}} \iff \sigma(n)=\sum_{d|n}d \]
线性筛 \({\rm{d}}\)

设 \(n=\prod_{i=1}^mp_i^{c_i}\) ，则根据乘法原理有：

\[{\rm{d}}(n)=\prod_{i=1}^m(c_i+1) \]
  • 对于质数 \(p\) ，有 \({\rm{d}}(p)=2\) 。
  • 对于 \(a,b\) 满足 \(a\bot b\) ，有 \({\rm{d}}(ab)={\rm{d}}(a){\rm{d}}(b)\) 。
  • 对于质数 \(p\) 与合数 \(a\) 满足 \(p|a\) ，设 \(c\) 为 \(p\) 在 \(pa\) 中的次数，有 \({\rm{d}}(pa)={\rm{d}}(a)\frac{c+1}{c}\) 。

于是就可以线性筛了：

\(num_i\) 记录 \(i\) 的最小质因子的次数。

inline void sieve()
{
    d[1]=1;
    for(int i=2;i<=N;++i)
    {
        if(!flag[i]) prime[++cnt]=i,d[i]=2,num[i]=1;
        for(int j=1;j<=cnt&&i*prime[j]<=N;++j)
        {
            flag[i*prime[j]]=true;
            if(i%prime[j])
            {
                num[i*prime[j]]=1;
                d[i*prime[j]]=d[i]*2;
            }
            else
            {
                num[i*prime[j]]=num[i]+1;
                d[i*prime[j]]=d[i]/num[i*prime[j]]*(num[i*prime[j]]+1);
                break;
            }
        }
    }
}
线性筛 \(\sigma\)

由乘法原理得：

\[\sigma(n)=\prod_{i=1}^m\sum_{j=0}^{c_i}p_i^j \]

令 \(f\) 记录约数和，\(g\) 记录最小质因子 \(p\) 的 \(\sum_{i=0}^{c}p^i\) 。则有：

  • 对于质数 \(p\) ，有 \(f(p)=1+p,g(n)=1+p\) 。
  • 对于 \(a,b\) 满足 \(a \bot b\) ，且 \(ab\) 的最小质因子为 \(p\) ，有 \(f(ab)=f(a)f(b),g(ab)=\sum_{i=0}^{c}p^i\) 。
  • 对于质数 \(p\) 和合数 \(a\) 且 \(p\) 是 \(a\) 的最小质因子，有 \(g(pa)=g(a)\times p+1,f(pa)=f(a)\frac{g(pa)}{g(a)}\) 
inline void sieve()
{
    f[1]=g[1]=1;
    for(int i=2;i<=N;++i)
    {
        if(!flag[i]) prime[++cnt]=i,f[i]=g[i]=1+i;
        for(int j=1;j<=cnt&&i*prime[j]<=N;++j)
        {
            flag[i*prime[j]]=true;
            if(i%prime[j])
            {
                f[i*prime[j]]=f[i]*f[prime[j]];
                g[i*prime[j]]=1+prime[j];
            }
            else
            {
                g[i*prime[j]]=g[i]*prime[j]+1;
                f[i*prime[j]]=f[i]/g[i]*g[i*prime[j]];
                break;
            }
        }
    }
}

欧拉函数

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

设 \(n=\prod_{i=1}^mp_i^{c_i}\) ，则有通式：

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

有：

\[\varphi * {\rm{I}}={\rm{id}} \]

证明：

因为 \(\varphi\) 是积性函数，所以只需要证明 \(n=p^c\) 的情况，即证明：

\[(\varphi*{\rm{I}})(n)=\sum_{d|n}\varphi(d)={\rm{id}}(n) \]

因为 \(n=p^c\) 所以 \(d=1,p,p^2,p^3 \cdots,p^c\) ，将上式改为枚举 \(p\) 的次数：

\[\begin{align} \sum_{d|n}\varphi(d)&=\sum_{i=0}^c\varphi(p^i)\\ &=1+p^0(p-1)+p^1(p-1)+\cdots+p^{c-1}(p-1)\\ &=p^c\\ &={\rm{id}}(n) \end{align} \]

上面用到了欧拉函数的性质： \(\varphi(p^c)=p^{c-1}(p-1)\) 。

\(\varphi*{\rm{I}}={\rm{id}}\) 得证。

线性筛 \(\varphi\)
  • 对于质数 \(p\) ，有 \(\varphi(p)=p-1\) 。
  • 对于 \(a,b\) 满足 \(a\bot b\) ，有 \(\varphi(ab)=\varphi(a)\varphi(b)\) 。
  • 对于质数 \(p\) 和数 \(a\) 满足 \(p|a\) ，有 \(\varphi(pa)=\varphi(a)\times p\) 。

对于第三种情况，证明如下：

因为 \(p|a\) ，所以 \(a\) 包含了所有 \(pa\) 的质因子，则有：

\[\begin{align} \varphi(pa)&=p\times a\prod_{i=1}^m\frac{p_i-1}{p_i}\\ &=p\times\varphi(a) \end{align} \]

证毕。

inline void sieve()
{
	phi[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!flag[i]) prime[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt&&prime[j]*i<=N;j++)
		{
			flag[prime[j]*i]=true;
			if(i%prime[j]==0)
			{
				phi[prime[j]*i]=phi[i]*prime[j];
				break;
			}
			else phi[prime[j]*i]=phi[i]*(prime[j]-1);
		}
	}
}

莫比乌斯函数

\[\mu(n)=\begin{cases}1 & n=1\\ 0 & \exists d>1:d^2|n \\ (-1)^{\omega(n)} & \text{otherwise}\end{cases} \]

其中 \(\omega(n)\) 表示 \(n\) 不同质因子个数。

有：

\[\sum_{d|n}\mu(d)=\epsilon(n) \iff \epsilon=\mu*{\rm{I}} \]

证明：

令 \(n=\prod_{i=1}^mp_i^{c_i},n'=\prod_{i=1}^mp_i\) ，则：

\[\begin{align} \sum_{d|n}\mu(d)&=\sum_{d|n'}\mu(d)\\ &=\sum_{i=0}^m{m \choose i}\times 1\times (-1)^i\\ &=(1+(-1))^k\\ &=\begin{cases}1 & k=0 \\ 0 & k \not =0\end{cases}\\ &=\begin{cases}1 & n=1 \\ 0 & n \not =1\end{cases}\\ &=\epsilon(n) \end{align} \]

这同时也证明了 \(\epsilon=\mu*{\rm{I}}\) 。

证毕。

与欧拉函数结合，有：

\[\varphi=\mu*{\rm{id}} \iff \varphi(n)=\sum_{d|n}d\cdot\mu(\frac{n}{d}) \]

证明：

\[\varphi*{\rm{I}}={\rm{id}} \iff \varphi*{\rm{I}}*\mu={\rm{id}}*\mu \iff \varphi=\mu*{\rm{id}} \]

上面用到了 \(\mu*{\rm{I}}=\epsilon\) 的结论。

证毕。

反演结论
\[[{\rm{gcd}}(i,j)=1] \iff \sum_{d|i,d|j}\mu(d) \]
线性筛 \(\mu\)
  • 对于质数 \(p\) ，有 \(\mu(p)=-1\) 。
  • 对于 \(a,b\) 满足 \(a\bot b\) ，有 \(\mu(ab)=\mu(a)\mu(b)\) 。
  • 对于质数 \(p\) 和整数 \(a\) 满足 \(p|a\) ，有 \(\mu(pa)=0\) 。 
inline void sieve()
{
    mu[1]=1;
	for(int i=2;i<=N;++i)
	{
		if(!flag[i]) prime[++cnt]=i,mu[i]=-1;
		for(int j=1;j<=cnt&&i*prime[j]<=N;++j)
		{
			flag[i*prime[j]]=true;
			if(!(i%prime[j])) break;
			mu[i*prime[j]]=-mu[i];
		}
	}
}

参考资料：

莫比乌斯反演 - OI Wiki

筛法 - OI Wiki