数论函数定义 (数论函数)

数论函数的定义:在全体正整数（或者整数）上定义的函数称作数论函数。积性的定义：若 gcd(a,b)=1,则f(ab)=f(a)f(b)。举个栗子: 欧拉函数 $\varphi (x)$ : 1(x)=1,Id(x)=x,I(x)=[x=1]

。接下来,我们再举一个函数,狄利克雷卷积: 数论函数f(n)和g(n)的狄利克雷卷积h(n)定义为： $h(n)=\sum_{d|n}^{}f(d)g(\frac{n}{d})$ 记作h=f*g; 定理:两个积性函数的狄利克雷卷积也是积性函数。那我们是如何证明的呢,那可就说来话长了: $h(xy)=\sum_{d_{1}|x}^{}f(d_{1})g(\frac{x}{d_{1}})=\sum_{d_{1}|x}^{}\sum_{d_{2}|y}^{}f(d_{1}d_{2})g(\frac{xy}{d_{1}d_{2}})=\sum_{d_{1}|x}^{}f(d_{1})g(\frac{x}{d_{1}})\sum_{d_{2}|y}^{}f(d_{2})g(\frac{y}{d_{2}})=h(x)h(y)$ 看到这么长一串的函数,我的心就发抖……… 定理:两个积性函数的对应位置相乘也是积性函数。这个就很显然了,证明我就不给出来了,你们自己想着吧。所以我们可以定义更多的数论函数，以及用卷积描述它们之间的关系：例如: $d(x)=\sum$ $_{d|n}$ 1,即 d=1*1

$n=\sum$ $_{d|n}\varphi (d)$ ,即 $Id=\varphi *1$ 接下来,我们来研究一下,卷积的性质: 定理(卷积运算律): 交换律：设有两个积性函数f,g则 f*g=g*f

结合律：设有两个积性函数f,g,h则 (f*g)*h=f*(h*g)

这不就是乘法结合律吗?小学生都会好不好…… 交换律的证明很显然。结合律的证明可以把式子改写成矩阵形式，然后用矩阵的结合律来证明。应该大力推式子也可以。单位元的定理: I是单位元:对任意的数论函数 f,f*I=I*f=f

; 证明过程如下: $f(n)=\sum_{d|n}^{})f(d)I(\frac{n}{d})$ 接下来又来到了下一个函数,狄利克雷逆: 若 f*g=I

,则数论函数f,g互为彼此的狄利克雷逆。

整数分块

接下来,我们进入下一个章节的学习:整数分块

定理:对于任意的, $\left \lfloor \frac{n}{i} \right \rfloor$ 只有 $O(\sqrt{n})$ 种取值

证明过程如下:

当 $1\leq i\leq \sqrt{n}$ 时, $\frac{n}{i}$ 只有 $O(\sqrt{n})$ 种取值

当 $i> \sqrt{n}$ 时, $\frac{n}{i}\leq \sqrt{n}$ ,也只有 $O(\sqrt{n})$ 种取值

综上,只有 $O(\sqrt{n})$ 种取值

下面举个栗子:

计算下取整分式的和式,计算 $\sum$ $_{i}^{n}=1\left \lfloor \frac{n}{i} \right \rfloor$

由于 $\left \lfloor \frac{n}{i} \right \rfloor$ 只有 $O(\sqrt{n})$ 种取值 ,并且,使得 $\left \lfloor \frac{n}{i} \right \rfloor$ 取相同的取值的也是一段一段的，所以我们只需要一段一段地计算即可。

res=0;
for(int l=1,r;l<=n;l=r+1){r=n/(n/l);res+=(r-l+1)*(n/l);
}

哎哟,终于讲完了,累死我了,咱么今天就讲到这里,下篇博文我们会讲莫比乌斯反演,记得来收看哦!!

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：wireshark练习抓取网络数据包用C编程完成modbus协议，从云端服务器读取温湿度数据。

下一篇：MybatisPlus详解 | DQLDML快速开发... | 系统性学习 | 无知的我费曼笔记

数论专题(1)数论函数,整数分块

数论函数定义 (数论函数)

整数分块

相关内容

热门资讯