数论函数
在数论上，算术函数（或称数论函数）指定义域为正整数、陪域为复数的函数，每个算术函数都可视为复数的序列。
最重要的算术函数是积性及加性函数。算术函数的最重要操作为狄利克雷卷积，对于算术函数集，以它为乘法，一般函数加法为加法，可以得到一个阿贝尔环。
---百度百科
就是定义域为正整数，值域是一个数集
定义数论函数运算：
两个数论函数相等，即他们的每一项都相等
加法：\((\mathbf{f}+\mathbf{g})(i) = \mathbf{f}(i)+\mathbf{g}(i)\)
数乘：\((x\mathbf{f})(i)=x\cdot \mathbf{f}(i)\)
狄利克雷卷积
狄利克雷乘积(Dirichlet product)亦称狄利克雷卷积、卷积，是数论函数的重要运算之一。设f(n)、g(n)是两个数论函数，它们的Dirichlet(狄利克雷)乘积也是一个数论函数，简记为h(n)=f(n)*g(n)。
---百度百科
定义两个数论函数的狄利克雷卷积符号： \(\ast\)
令
则
或者表示为：
性质：
1.交换律
2.结合律
证明：
3.分配率
证明：
4.数乘关系
证明略
5.单位元
令
那么
不妨定义\([P]\)表示：当\(P\)为真时，式子的值为\(1\)，否则为\(0\)
那么
6.逆元
对每个\(\mathbf{f}(1) \neq 0\)的函数\(f\) ，都存在一个函数\(\mathbf{g}\)使得\(\mathbf{f}*\mathbf{g}=\epsilon\)
如何求一个函数的逆？
定义
则
积性函数
积性函数指对于所有互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数。
完全积性函数：对于任意整数a和b有性质f(ab)=f(a)f(b)的数论函数。
---百度百科
如果一个数论函数\(f\)满足：对于\(n\bot m\)，有\(\mathbf{f}(nm)=\mathbf{f}(n)\mathbf{f}(m)\)，那么称这个函数为积性函数
常见的积性函数有：
\(\epsilon(n)=[n=1],\mathbf{f}(n)=n,\mathbf{f}(n)=n^k\)
事实上，他们满足完全积性，也就是说不论是否有\(n \bot m\)，都有\(\mathbf{f}(nm)=\mathbf{f}(n)\mathbf{f}(m)\)
另外两个常见的积性函数为\(\sigma_0\)和\(\phi\)
其中\(\sigma_0(n)\)表示\(n\)的因数个数，\(\phi(n)\)表示\([1,n]\)中与\(n\)互质的数的个数
容易知道：对于质数\(p\)和正整数\(k\)
(埋个伏笔，下面要用到)
积性的证明：
\(\forall \ n\bot m,n,m\in \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}}\)
若\(n\bot m\)，则对于\(nm\)的每一个约数\(t\)，都可以表示成\(n\)的一个约数乘\(m\)的一个约数的形式。即\(t=gcd(n,t)\times gcd(m,t)\)
由乘法原理可知：
\(\forall \ n\bot m,n,m\in \mathbb{Z_+}, \phi(nm)=\phi(n)\phi(m)\)：
\(n\bot m,t\bot nm\iff t\bot n,t\bot m\iff (t\ mod\ n)\bot n,(t\ mod\ m)\bot m\)
则 \(\forall\ t\in [1,nm],t\bot nm\)，都可以对应到一个\([1,n]\)的与\(n\)互质的数\(t\ mod\ n\)和一个\([1,m]\)的与\(m\)互质的数\(t\ mod\ m\)
同上可知
接下来证明一个重要的结论：两个积性函数的狄利克雷卷积也是一个积性函数
有两个需要用到的性质
1.若\(n\bot m\)，则每个\(nm\)的约数都可以分解成一个\(n\)的约数和一个\(m\)的约数的积(上面讲到过)
2.若\(n\bot m,a\bot n,b\bot m\)，则\(a\bot b\)(互质的性质)
则对于\(n\bot m\)，有：
另一个结论：积性函数的逆也是积性函数 (证明略)
积性函数的用途：
线性筛(实际上是利用线性筛求积性函数的值)
唯一分解定理：\(\forall \ n \in \mathbb{Z_+} ,n=\prod\limits_{i=1}^{t}p_i^{k_i}(p_i为质数，k_i为正整数)\)
那么有
于是我们就有另一种方法表示积性函数，即给出它在素数幂处的取值
当我们在线性筛的时候可以求出每个数的最小质因数\(p_1\)，它的次数\(k_1\)，那么
由上面的结论可知：
(下面的那个是不是有点熟悉？就是课本上欧拉函数的求法)
莫比乌斯反演
我们定义\(1\)(\(1\)是一个数论函数)的逆是\(\mu\)，那么由定义知\(1*\mu=\epsilon\)
那么如果\(\mathbf{g}=\mathbf{f}*1,则\mathbf{f}=\mathbf{f}*1*\mu=\mathbf{g}*\mu\)(单位元的定义)
也就是
当然还有另一个方向的莫比乌斯反演(这个大概更常用)
(证明略)
如何求\(\mu\)?
由于\(1\)是积性的，所以\(1\)的逆\(\mu\)也是积性的，则
求\(\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];
}
}
}