从积性函数到莫比乌斯反演
本文最后更新于:2022年10月5日 下午
从积性函数到莫比乌斯反演
呜呜呜,为了数论课不做大牢,学数论!
简单介绍
数论函数
数论函数,简单来说就是定义域是\(\mathbb{N^{*}}\)的函数,可以视为一个数列
积性函数
定义
积性函数是一类特殊的数论函数,它满足以下性质 \[ f(1) = 1.\ \forall i, j\in\mathbb{N^{*}},gcd(i,j)=1: f(i*j)=f(i)*f(j) \] 特别的
若积性函数被称为完全积性函数,若它满足以下性质 \[ \forall i,j\in \mathbb{N^{*}}:f(i*j)=f(i)*f(j) \]
性质
设\(f\),\(g\)为积性函数,则 \[ h(x)=f(x)*g(x),\ h(x)=f(x^{p}),\ h(x)=f^{p}(x),\ h(x)=\sum_{d|x}f(d)g(\frac{x}{d}) \] 也为积性函数
特别的,根据唯一分解定理,设\(x=\prod p_i^{k_i}\),若\(F\)为积性函数,则有 \[ F(x)=\prod F(p_i^{k_i}) \] 若\(F\)为完全积性函数,则有 \[ F(x)=\prod F^{k_i}(p_i) \]
例子
恒等函数\(id(n) \equiv n\)
单位函数\(\epsilon (n)=[n=1]\)
常数函数\(1(n)\equiv 1\)
因子和函数\(\delta(n)=\sum_{d|n}d\)
因子个数函数\(\tau(n)=\sum_{d|n}1\)
一般的,除数函数\(\sigma_k(n)=\sum_{d|n}d^k\)
欧拉函数\(\phi(n)=\sum_{i=1}^n[gcd(i,n)=1]\),即\(n\)的与\(n\)互质的因数的个数
莫比乌斯函数,其中\(n=\prod_{i=1}^r p_i^{k_i}\) \[ \mu(n)=\begin{cases} 1,n=1\\ 0,\exists i, s.t.k_i>=2\\ (-1)^r,otherwise \end{cases} \] 值得指出的是,上述前三个函数为完全积性函数
\(Dirichlet\)卷积
定义
设\(f\)和\(g\)为数论函数,则两者的\(Dirichlet\)卷积\(f*g\)定义如下 \[ f*g(n):=\sum_{d|n}f(d)g(\frac{n}{d}) \]
性质
\(f\),\(g\),\(h\)为数论函数
单位元存在性
\(\forall f, \exists \epsilon :f*\epsilon \equiv f\)
逆元唯一性
若\(\exists g, s.t.f*g\equiv\epsilon\),则称\(g\)为\(f\)的逆元,事实上,逆元唯一
交换律
\(f*g=g*f\)
结合律
\(f*(g*h)=(f*g)*h\)
分配律
\(f*(g+h)=f*g+f*h\)
恒等关系
\(f=g\iff f*h=g*h\)
重要结论
1.积性函数的卷积仍为积性函数
2.积性函数的逆元也为积性函数
例子
1.\(\epsilon=\mu*1\)
2.\(\tau=1*1\)
3.\(\delta=id*1\)
4.\(\phi=\mu*n\)
数论分块
数论分块可以用于快速求解带向下取整(显然也有整除)的和式,时间复杂度可以达到\(O(\sqrt n)\)
两个结论
1.\(\forall a,b,c\in\mathbb{Z}, \lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor=\lfloor\frac{a}{bc}\rfloor\)
2.\(\forall n\in\mathbb{N^*},|V|=\{\lfloor\frac{n}{d}\rfloor|\forall d, 1 \le d\le n\}| \le 2\lfloor\sqrt{n}\rfloor\)
所以可以枚举每个整数\(d\)对应的\(i\)的区间,来分块计算各个小区间对应的答案,最后相加就行,实现如下
实现
1 |
|
莫比乌斯反演
来到了,高一集训时的噩梦,\(cjq\)大仙的解方程猜测\(\mu\)函数现场,四年来念念不忘的Mobius Inversion
\(\mu\)函数的补充
\([gcd(i,j)=1]=\sum_{d|gcd(i,j)} {\mu(d)}\)
即\([gcd(i,j)=1]=\epsilon *gcd(i,j)\)
显然,如果\(gcd(i,j)=1\),那么d只能取\(1\),故和式为\(1\);若不然,\(gcd(i,j)\)的因子总是成对出现,故可取到的\(\mu\)中\((-1)^r\)的\(r\)总是连续的\(1-2n\),故结果为\(0\)
线性筛
线性筛可以用于求绝大部分积性函数(其实我也不知道有什么不能求的),区别只在于在线性筛过程中对函数值的处理计算
对于\(\mu\)函数,实现如下
实现
1 |
|
结论
\(f\)和\(g\)为两个数论函数,若 \[ f(n)=\sum_{d|n}g(d) \] 则有 \[ g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d}) \] \(f\)称为\(g\)的莫比乌斯变换,\(而g\)称为\(f\)的莫比乌斯反演,可以看出,\(f = g*1\)
那么,如果遇到 \[ \sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=1] \] 就可以转化为 \[ \sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,j)}{\mu(d)} \] 改变求和顺序,可以得到 \[ \sum_{d=1}\mu(d)\sum_{i = 1}^n[d|i]\sum_{j=1}^m[d|j] \] 显然后面两个求和号可以直接得出结果,故 \[ \sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=1]=\sum_{d=1}^{min(n,m)}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor \] 直接使用数论分块解决即可
实现
推导与上述无异,再使用二维容斥即可解决问题
即计算 \[ \sum_{d=1}^{min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor \] 令\(n=b,m=d;n=b,m=c-1;n=a-1,m=d;n=a-1,m=c-1\)四种情况即可
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!