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

admin

2024-05-01 14:45:16

0次

从今天起,我们将要开始数论的学习,是不是感觉很难?难的话就听我讲吧,讲了后就不难了(bushi)

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

数论函数的定义:在全体正整数（或者整数）上定义的函数称作数论函数。积性的定义：若 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”。

上一篇：北京3小时抵达，11个城市马上出发！北京3个小时到广州北京3-4小时就能到的地方

下一篇：半场-青岛西海岸0-2南通支云西海岸后防两次失误戈迪内斯双响南通支云戈迪内斯头球南通支云戈迪内斯近况

热门资讯

解密科技赛道超额收益！顶尖基金... 2026年以来A股结构性行情极致演绎，主动权益基金业绩严重分化。数据显示，截至7月3日，主动权益基金...

证券板块为什么是“股市风向标”... 资本市场的长期投资价值对于证券公司的长期投资价值具有显著的正向带动作用。从收入构成中我们能够看到证券...

原创年... 46% 的 Z 世代、35% 的千禧一代，延后了买房、结婚、生育这些人生重大决策。听起来有点惨，但...

消息称SambaNova融资1... IT之家 7 月 8 日消息，据彭博社稍早前消息，AI 芯片企业 SambaNova 即将在当地时间...

利好突袭！A股盘中，直线拉升！... 云计算概念股异动！今日（7月8日），云计算概念股集体拉升，板块指数涨幅超过4%，浪潮信息一字涨停，...

原创传... 这几年喊了多年的美元霸权衰落，终于不再是空话。美国自己急得团团转，四处找新的货币锚点，还真折腾出几个...

韩国股市跌入技术性熊市，监管紧... 韩国股市正面临今年以来最严峻的考验，基准指数KOSPI从历史高点下跌20%，进入技术性熊市门槛，监管...

原创美... 网上一直流传着一组扎心数据，即：中国居民可支配收入仅占GDP的比例45%左右，而美国却高达75%以上...

AI休整期不悲观，某些板块底部... 继续普调，严重缩量！今日沪指跌1.26%、创业板跌0.94%、科创综指跌0.18%；全天成交额...

知名经济学家高善文去世，曾预判... 出品｜搜狐财经作者｜汪梦婷 7月7日，知名经济学家、原国投证券首席经济学家高善文不幸去世，享年55...

20万份文件泄密，苹果被坑惨了苹果的机密在印度代工厂塔塔电子大面积泄露后，坐不住的不仅是库克，还有新德里的高官们。当地时间7月2...

起点订购APP贵金属订购交易欺... 　　互联网上充斥着白银、铂金、铜等现货贵金属投资公司的宣传，通过不实的贵金属现货APP吸引投资者，但...

全新易购APP高额手续费的期货... 　　全新易购APP白银铂金现货订购出现严重的损失，投资者在这个平台根本赚不到钱，开始还好，后面的交易...

银行板块震荡上扬中国银行等股... 观点网讯：7月8日，银行板块震荡上扬，中国银行、农业银行、建设银行、成都银行、工商银行等股纷纷上扬。...

AI Agent进入深水区：企... AI Agent从技术概念走向商业落地，企业付费意愿成为检验产品价值的唯一标准。过去两年大量AI创业...

一通智投APP内幕交易欺骗投资... 　　一通智投APP虚假现货订购交易为非法期货，投资者被宣传广告给诱导，下载了一通智投APP，结果在这...

港股科技股全线大涨！跌多了是基... 港股市场近日整体有明显反弹的科技股今日再度集体走强，恒生科技指数拉升涨超3%。个股中，联想涨超8%，...

一场博览会，看透低空经济风口全... 文丨许佳慧低空经济风起，谁是真正的弄潮儿？【观赛道：题材风口开启，全链布局成型】低空经济有多火...

黄金单边牛市没那么快回来？预测... 黄金这波反弹刚冒头，没人敢直接砸重仓赌方向。Polymarket上的交易显示，黄金7月触及4300美...

超颖电子布局“A+H”：一季度... 瑞财经吴文婷7月6日，超颖电子发布公告称，为满足公司业务发展需要，深入推进国际化战略，打造国际化资...

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

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

整数分块

相关内容

热门资讯