数论专题(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南通支云西海岸后防两次失误戈迪内斯双响南通支云戈迪内斯头球南通支云戈迪内斯近况

热门资讯

嘉兴银行“新帅”确定：行长王芳... 嘉兴银行“新帅”确定：行长王芳升任党委书记人民财讯5月19日电，据嘉兴银行消息，嘉兴市委常委、常务...

这届年轻人的置业逻辑变了！报告... 5月18日，58同城、安居客发布《2026青年置业报告》。这份基于数千名20-35岁年轻人的调研，揭...

金融让生活更美好|上银财富“5... 为更好地满足广大客户多元化、多层次的财富保值增值需求，上海银行于5月18日正式启动“518财富理想节...

追觅俞浩回应设立上百个BU：A... 来源：中国企业家做企业不是开故事会，发展才能解释问题，发展才能解决问题文|《中国企业家》记者 ...

原创强... 2026年5月13日，深圳。华为和总资产1.5万亿的中国中化，正式签下一份深化战略合作协议。一家...

金价，还在跌！警惕骗局—— 5月18日早盘，现货黄金短时下跌，失守4500美元/盎司，为3月底以来首次。【此前报道：】5月19...

中国电信：选举柯瑞文为董事长；... 据每日经济新闻：5月19日，中国电信（601728.SH）公告称，公司第九届董事会第一次会议选举柯瑞...

2026第六届中国贵州国际能源... 5月18日，2026第六届中国贵州国际能源产业博览交易会（简称“贵州能博会”）在贵阳国际会议展览中心...

华为轮值董事长徐直军访问东风汽... 2026年5月19日，华为轮值董事长徐直军，华为公司高级副总裁、引望公司CEO靳玉志一行到访东风汽车...

20cm股热度渐升！涨停数追平... 财联社5月19日讯（编辑梓隆），近期，创业板、科创板股热度较高，截至今日（5月19日）收盘，累计共...

原创告... 1499，这个数字陪了我们好几年。买飞天茅台的人，对它太熟悉了。可就在3月30日晚上，贵州茅台一纸公...

美国30年期国债收益率升至20... 美国30年期国债收益率上升至5.177%，为2007年以来的最高水平。 (本文来自第一财经)

5连板威龙股份：存在公司股价上...

一人掌控2家国产存储龙头，57... 一个老板，左手握着国内芯片设计龙头兆易创新，右手攥着国产DRAM市场第一的长鑫科技，57亿关联交易深...

跟宇树一比，云深处太贵了？营收仅宇树五分之一，估值倍数贵了约60%。 AIX财经（AIXcaijing）原创作者｜王汉星编...

华曦达将在港交所上市：业绩波动... 来源|贝多商业&贝多财经 5月18日，深圳市华曦达科技股份有限公司（下称“华曦达”，HK:00901...

微纳星空科创板IPO拟募资50... 上交所&深交所新股上市 5月12日-5月18日，上交所无公司上市；深交所主板有2家公司上市。...

突发！伊朗股市，重新开市！特朗... 刚刚，伊朗股市恢复交易！据央视新闻报道，当地时间5月19日，伊朗德黑兰证券交易所恢复股票交易。目前...

龙湖完成“21龙湖04”本息兑... 5月19日，龙湖集团如期完成“21龙湖04”的本金兑付与付息，涉及总金额约15.54亿元，包含本金1...

600759，连续12个跌停【导读】市场情绪整体不错！中国基金报记者泰勒大家好啊，今天的市场，尽管外围行情似乎风雨飘摇，但...

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

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

整数分块

相关内容

热门资讯