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

数论函数的定义:在全体正整数（或者整数）上定义的函数称作数论函数。积性的定义：若 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互为彼此的狄利克雷逆。

整数分块

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

定理:对于任意的 $i$ , $\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$ 取相同的取值的 $i$ 也是一段一段的，所以我们只需要一段一段地计算即可。

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”。

上一篇：对外包催收机构管理不严，兴业银行信用卡中心被责令改正、罚款40万元兴业银行信用卡中心内部催收兴业银行信用卡催收部门

下一篇：长沙一宗商业地块挂牌！长沙挂牌两宗商业地块长沙华狮棚改地块挂牌

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

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

整数分块

相关内容

热门资讯