狄利克雷卷积与莫比乌斯反演

数论函数

在数论上，算术函数（或称数论函数）指定义域为正整数、陪域为复数的函数，每个算术函数都可视为复数的序列。

最重要的算术函数是积性及加性函数。算术函数的最重要操作为狄利克雷卷积，对于算术函数集，以它为乘法，一般函数加法为加法，可以得到一个阿贝尔环。

---百度百科

[mathbf{f}(x),x in mathbb{N_+}, mathbf{f}(x)in C ]

就是定义域为正整数，值域是一个数集

定义数论函数运算：

两个数论函数相等，即他们的每一项都相等

加法：((mathbf{f}+mathbf{g})(i) = mathbf{f}(i)+mathbf{g}(i))

数乘：((xmathbf{f})(i)=xcdot mathbf{f}(i))

狄利克雷卷积

狄利克雷乘积(Dirichlet product)亦称狄利克雷卷积、卷积，是数论函数的重要运算之一。设f(n)、g(n)是两个数论函数，它们的Dirichlet(狄利克雷)乘积也是一个数论函数，简记为h(n)=f(n)*g(n)。

---百度百科

定义两个数论函数的狄利克雷卷积符号： (ast)

令

[mathbf{t}=mathbf{f}ast mathbf{g} ]

则

[mathbf{t}(n) = sumlimits _{ij=n} mathbf{f}(i)mathbf{g}(j) ]

或者表示为：

[mathbf{t}(n)=sumlimits_{i|n}mathbf{f}(i)mathbf{g}(frac{n}{i}) ]

性质：

1.交换律

[mathbf{f}*mathbf{j} = mathbf{j} * mathbf{f} ]

2.结合律

[(mathbf{f}*mathbf{g})*mathbf{h}=mathbf{f}*(mathbf{g}*mathbf{h}) ]

证明：

[sumlimits_{(ij)k=n}(mathbf{f}(i)mathbf{g}(j))mathbf{h}(k)=sumlimits_{i(jk)=n}mathbf{f}(i)(mathbf{g}(j)mathbf{h}(k)) ]

3.分配率

[(mathbf{f}+mathbf{g})*mathbf{h}=mathbf{f}*mathbf{h}+mathbf{g} *mathbf{h} ]

证明：

[sumlimits _{ij=n}(mathbf{f}(i)+mathbf{g}(i))cdot mathbf{h}(i)=sumlimits_{ij=n} mathbf{f}(i)cdot mathbf{h}(i) + sumlimits_{ij=n} mathbf{g}(i)cdot mathbf{h}(i) ]

4.数乘关系

[(xcdot mathbf{f}) * mathbf{g} = x(mathbf{f} * mathbf{g}) ]

证明略

5.单位元

令

[epsilon (n)= egin{cases} 1, &n=1\ 0, &n>1 end{cases} ]

那么

[mathbf{f}*epsilon\ =sumlimits_{i|n}mathbf{f}(i)epsilon(frac{n}{i})\ =mathbf{f} ]

[epsilon *mathbf{f} = mathbf{f} ]

不妨定义([P])表示：当(P)为真时，式子的值为(1)，否则为(0)

那么

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

6.逆元

对每个(mathbf{f}(1) eq 0)的函数(f) ，都存在一个函数(mathbf{g})使得(mathbf{f}*mathbf{g}=epsilon)

如何求一个函数的逆？

定义

[mathbf{g}(n)=frac{1}{mathbf{f}(1)} left([n=1]- sumlimits_{ij=n,i eq 1}mathbf{f}(i)mathbf{g}(j) ight) ]

则

[mathbf{f}(i)*mathbf{g}(i)\ =sumlimits_{ij=n}mathbf{f}(i)mathbf{g}(j)\ =mathbf{f}(1)mathbf{g}(n)+sumlimits_{ij=n,i eq 1}mathbf{f}(i)mathbf{g}(j)\=[n=1] ]

积性函数

积性函数指对于所有互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数。

完全积性函数：对于任意整数a和b有性质f(ab)=f(a)f(b)的数论函数。

---百度百科

如果一个数论函数(f)满足：对于(not m)，有(mathbf{f}(nm)=mathbf{f}(n)mathbf{f}(m))，那么称这个函数为积性函数

常见的积性函数有：

(epsilon(n)=[n=1],mathbf{f}(n)=n,mathbf{f}(n)=n^k)

事实上，他们满足完全积性，也就是说不论是否有(n ot m)，都有(mathbf{f}(nm)=mathbf{f}(n)mathbf{f}(m))

另外两个常见的积性函数为(sigma_0)和(phi)

其中(sigma_0(n))表示(n)的因数个数，(phi(n))表示([1,n])中与(n)互质的数的个数

容易知道：对于质数(p)和正整数(k)

[sigma_0(p^k)=k+1\ phi(p^k)=p^{k-1}(p-1) ]

(埋个伏笔，下面要用到)

积性的证明：

(forall not m,n,min mathbb{Z_+} ,sigma_0(nm)=sigma_0(n)sigma_0(m))：

对于(n,m)，设(n=p_{a1}^{k_{a1}}p_{a2}^{k_{a2}}...p_{an}^{k_{an}},m=p_{b1}^{k_{b1}}p_{b2}^{k_{b2}}...p_{bm}^{k_{bm}})

若(not m)，则对于(nm)的每一个约数(t)，都可以表示成(n)的一个约数乘(m)的一个约数的形式。即(t=gcd(n,t) imes gcd(m,t))

由乘法原理可知：

[sigma_0(nm)=sigma_0(n)sigma_0(m) ]

(forall not m,n,min mathbb{Z_+}, phi(nm)=phi(n)phi(m))：

(not m,tot nmiff tot n,tot miff (t mod n)ot n,(t mod m)ot m)

则 (forall tin [1,nm],tot nm)，都可以对应到一个([1,n])的与(n)互质的数(t mod n)和一个([1,m])的与(m)互质的数(t mod m)

同上可知

[phi(nm)=phi(n)phi(m) ]

接下来证明一个重要的结论：两个积性函数的狄利克雷卷积也是一个积性函数

有两个需要用到的性质

1.若(not m)，则每个(nm)的约数都可以分解成一个(n)的约数和一个(m)的约数的积(上面讲到过)

2.若(not m,aot n,bot m)，则(aot b)(互质的性质)

则对于(not m)，有：

[mathbf{t}(nm)\ =sumlimits_{d|nm} mathbf{f}(d)mathbf{g}(frac{nm}{d})\ =sumlimits_{a|n,b|m}mathbf{f}(ab)mathbf{g}(frac{nm}{ab})\ =sumlimits_{a|n,b|m}mathbf{f}(a)mathbf{f}(b)mathbf{g}(frac{n}{a})mathbf{g}(frac{m}{b})\ =left( sumlimits_{a|n}mathbf{f}(a)mathbf{g}(frac{n}{a}) ight) left( sumlimits_{b|m}mathbf{f}(b)mathbf{g}(frac{m}{b}) ight)\ =mathbf{t}(n)mathbf{t}(m) ]

另一个结论：积性函数的逆也是积性函数 (证明略)

积性函数的用途：

线性筛(实际上是利用线性筛求积性函数的值)

唯一分解定理：(forall n in mathbb{Z_+} ,n=prodlimits_{i=1}^{t}p_i^{k_i}(p_i为质数，k_i为正整数))

那么有

[mathbf{f}(n)=prodlimits_{i=1}^tmathbf{f}(p_i^{k_i}) ]

于是我们就有另一种方法表示积性函数，即给出它在素数幂处的取值

当我们在线性筛的时候可以求出每个数的最小质因数(p_1)，它的次数(k_1)，那么

[mathbf{f}(n)=mathbf{f}(p_1^{k_1})mathbf{f}(frac{n}{p_1^{k_1}}) ]

由上面的结论可知：

[sigma_0(n)=prodlimits_{i=1}^t(k_i+1)\ phi(n)=prodlimits_{i=1}^tp_i^{k_i-1}(p_i-1)=nprodlimits_{i=1}^t(1-frac{1}{p_i}) ]

(下面的那个是不是有点熟悉？就是课本上欧拉函数的求法)

莫比乌斯反演

我们定义(1)((1)是一个数论函数)的逆是(mu)，那么由定义知(1*mu=epsilon)

那么如果(mathbf{g}=mathbf{f}*1,则mathbf{f}=mathbf{f}*1*mu=mathbf{g}*mu)(单位元的定义)

也就是

[mathbf{g}(n)=sumlimits_{d|n}mathbf{f}(d)iffmathbf{ f}(n)=sumlimits_{d|n}mu(frac{n}{d})mathbf{g}(d) ]

当然还有另一个方向的莫比乌斯反演(这个大概更常用)

[mathbf{g}(n)=sumlimits_{n|d}mathbf{f}(d)iff mathbf{f}(n)=sumlimits_{n|d}mu(frac{d}{n})mathbf{g}(d) ]

(证明略)

如何求(mu)?

由于(1)是积性的，所以(1)的逆(mu)也是积性的，则

[mu(p^k) egin{cases} 1,&k=0\ -1,&k=1\ 0,&k>1 end{cases} ]

[mu(x)=egin{cases} 1,&x=1\ (-1)^n, &x=prodlimits_{i=1}^np_i\ 0,&其余情况 end{cases} ]

求(mu)的函数：

void get_mu(int n)
{
    mu[1] = 1;
    for(int i = 2;i <= n; i++)
    {
        if(!vis[i])
		{
			pri[++cnt] = i;
			mu[i] = -1;
		}
        for(int j = 1; j <= cnt && pri[j] * i <= n; j++)
        {
            vis[pri[j] * i] = 1;
            if(i % pri[j] == 0) break;
            else mu[i * pri[j]] = -mu[i];
        }
    }
 }