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

热门资讯

蜻蜓订购APP贵金属订购非法期... 　　蜻蜓订购APP以"投资平台"名义对外宣传，主打贵金属期货（订购）交易。该平台一方面强调自身"正规...

悟空订购APP非法期货交易欺骗... 　　近期，有投资者反映，“悟空订购APP”等平台以白银、贵金属订购为名，宣传所谓“高收益”“低门槛”...

小赢淘金APP期货投资骗局，平... 　　“小赢淘金”之流，最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...

八方淘金APP非法期货交易欺骗... 　　警惕！八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易！　　...

智易购APP贵金属订购交易骗局... 　　很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传，很容易把智易购APP当成普...

喜玛银庄APP商品订购投资骗局... 　　喜玛银庄APP白银、铂金“现货订购”骗局警示：无资质平台涉嫌非法期货交易，投资者爆仓后如何维权？...

吉鑫乐享APP炒贵金属订购交易... 　　近期，多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损，甚至血本无归。看似正规的“...

易掘金APP虚假期货投资骗局，... 　　“易掘金”的APP它打着“高收益、灵活投资”的旗号，宣称通过“商品订购”就能轻松赚钱，吸引了不少...

在大吉订购APP订购交易亏损被... 　　近期，不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...

铂银壹号APP商品订购交易亏损... 　　许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道，殊不知这背后隐藏着巨大的合规风险...

兴鑫淘金APP贵金属订购交易亏... 　　白银、贵金属或其他商品类投资，除国家批准的正规期货交易场所及持牌期货公司外，市面上大量第三方交易...

铂银掘金APP无资质的违规平台... 　　铂银掘金等平台的投资者，往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引，进而下载...

八方淘金APP订购交易不合规，... 　　“八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名，实际采用高杠...

在指尖订购APP订购商品亏损被... 　　指尖订购APP这类平台，表面是“订购交易”，实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...

在犀贝易购APP做商品订购交易... 　　市面上打着“现货投资”“贵金属交易”旗号的APP并不少，但真正合规、受监管的平台并不多。犀贝易购...

易达淘金APP虚假商品订购交易... 　　易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号，实则通过不合规的交...

大浪淘金APP白银订购亏损被骗... 　　大浪淘金APP最隐蔽的套路，在于其完全封闭的内盘交易系统。表面上，它宣称与国际贵金属市场接轨；实...

一品好购APP上订购白银出现亏... 　　一品好购APP原名“一品订购”，运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...

九州订购APP贵金属订购投资骗... 　　九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告，用“5元起投”“充值返现”“0...

坚锅淘金APP交易软件并不正规... 　　当前，市面上大量所谓的“现货商城订购”交易软件，早已偏离了正常的实物商品买卖，演变为高杠杆、高手...

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

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

整数分块

相关内容

热门资讯