首页 > 其他分享 >数论分块扩展

数论分块扩展

时间:2024-08-30 22:25:12浏览次数:9  
标签:lfloor right frac 分块 数论 扩展 rfloor sqrt left

【OI-wiki #5805】feat(math/number-theory/sqrt-decomposition.md): 增加数论分块的拓展 & 改动部分格式

以计算含有 \(\left\lfloor\sqrt{\frac{n}{d}}\right\rfloor\) 的和式为例。考虑对于一个正整数 \(n\),如何求出集合

\[S=\left\{\left\lfloor\sqrt{\frac{n}{d}}\right\rfloor\mid d\in \mathbb{N}_{+}, d\leq n\right\} \]

的所有值,以及对每一种值求出哪些 \(d\) 会使其取到这个值。可以发现:

  1. 因为 \(\left\lfloor\sqrt{\frac{n}{d}}\right\rfloor\) 是单调不增的,所以对于所有 \(v\in S\),使得 \(\left\lfloor\sqrt{\frac{n}{d}}\right\rfloor=v\) 的 \(d\) 必然是一段区间。
  2. 对于任意正整数 \(t\leq n\),我们对 \(\leq t\) 与 \(>t\) 的 \(v\in S\) 分别分析,可以发现 \(t+n/t^2\geq |S|\),取 \(t=\sqrt[3]{n}\) 得到 \(|S|\) 的一个上界为 \(O(\sqrt[3]n)\)。

这些结论与数论分块所需的引理相似,因此猜测可以写为数论分块形式。

结论是:使得式子

\[\left\lfloor\sqrt{\frac{n}{p}}\right\rfloor=\left\lfloor\sqrt{\frac{n}{q}}\right\rfloor \]

成立的最大的 \(q\) 满足 \(p\leq q\leq n\) 为

\[\left\lfloor\frac{n}{\left\lfloor\sqrt{\frac{n}{p}}\right\rfloor^2}\right\rfloor \]

证明

令 \(v=\left\lfloor\sqrt{\frac{n}{p}}\right\rfloor=\left\lfloor\sqrt{\frac{n}{q}}\right\rfloor\),那么

\[\begin{aligned} v&\leq \sqrt{\frac{n}{q}}\\ v^2&\leq n/q\\ q&\leq n/v^2\\ q&\leq \left\lfloor n/v^2\right\rfloor \end{aligned} \]

同理 \(p\leq \left\lfloor n/v^2\right\rfloor\)。同时

\[\left\lfloor \sqrt\frac{n}{\left\lfloor n/v^2\right\rfloor}\right\rfloor\geq \left\lfloor \sqrt\frac{n}{n/v^2}\right\rfloor=\left\lfloor v\right\rfloor=v \]

又由 \(p\leq \left\lfloor n/v^2\right\rfloor\) 以及单调性可推出

\[v=\left\lfloor\sqrt{\frac{n}{p}}\right\rfloor\geq\left\lfloor \sqrt\frac{n}{\left\lfloor n/v^2\right\rfloor}\right\rfloor \]

所以

\[\left\lfloor\sqrt\frac{n}{\left\lfloor n/v^2\right\rfloor}\right\rfloor=v \]

所以 \(q=\left\lfloor n/v^2\right\rfloor\) 是最大的使得 \(\left\lfloor\sqrt{n/p}\right\rfloor=\left\lfloor\sqrt{n/q}\right\rfloor\) 成立的 \(q\)。

故原问题可以写为数论分块形式,代码与数论分块形式并无二异。

两个更加通用的结论

参照上方过程,可以同样地证明:

  1. 对于正整数 \(n\),使得式子 \(\left\lfloor\sqrt[\alpha]{n/p^\beta}\right\rfloor=\left\lfloor\sqrt[\alpha]{n/q^\beta}\right\rfloor\) 成立的最大的 \(q\) 满足 \(p\leq q\leq n\) 为 \(\left\lfloor\sqrt[\beta]{n/v^\alpha}\right\rfloor\),其中 \(v=\left\lfloor\sqrt[\alpha]{n/p^\beta}\right\rfloor\)。
  2. 对于正整数 \(n\),集合 \(\left\{\left\lfloor\sqrt[\alpha]{n/d^\beta}\right\rfloor\mid d\in \mathbb{N}_{+}, d\leq n\right\}\) 的大小的一个上界为 \(O(n^{1/(\alpha+\beta)})\)(大约为 \(2n^{1/(\alpha+\beta)}\))。

标签:lfloor,right,frac,分块,数论,扩展,rfloor,sqrt,left
From: https://www.cnblogs.com/caijianhong/p/18389613

相关文章

  • 【SpringBoot】分析 SpringBoot 中的扩展点
    1 前言SpringBoot它给我们留了很多的扩展点,这节我们就看看都有哪些(有的扩展点是基于Spring的,有的我就不具体强调到底是SpringBoot还是Spring的噢)。另外每一种扩展点我们都从两个方面来看:入口时机:入口就是SpringBoot解析或者寻找你自定义的类的时机执行时机:就是Spr......
  • TPAMI 2024 | 离散且平衡的谱聚类算法:一种可扩展的方法
    DiscreteandBalancedSpectralClusteringWithScalability离散且平衡的谱聚类算法:一种可扩展的方法RongWang,HuiminChen,YihangLu,QianrongZhang,FeipingNie,andXuelongLi摘要谱聚类(SC)因其卓越的聚类性能而成为深入研究的主要课题。尽管取得了成功......
  • 数论基础
    数论基础数论函数数论函数是指这样一类函数:其定义域是正整数,值域是一个数集。定义两个数论函数的加法,为逐项相加,即\((f+g)(n)=f(n)+g(n)\)。定义数乘这个数和每一项都相乘,即\((xf)(n)=x\timesf(n)\)。常见数论函数\[1(x)=1\\\epsilon(x)=[x=1]\\id(......
  • SpringMVC扩展点RequestBodyAdvice和ResponseBodyAdvice如何使用及实现原理
    1.概述  SpringMVC是当今web项目系统开发后端技术框架的不二之选,也是Spring全家桶中非常重要的一个成员,它的设计思想和实现套路都是很值得我们学习的,所以今天我们就再来看看SpringMVC框架中预留的两个钩子也就是扩展点:RequestBodyAdvice和ResponseBodyAdvice。之前在总结详解......
  • nginx扩展之支持多个ssl加密虚拟主机
    nginx支持一台服务器唯一IP:PORT,根据server_name创建区分多个经过ssl加密的https虚拟主机,apache不支持 生成www.magedu.net域名证书:[[email protected]]#cd/etc/pki/tls/certs/[[email protected]]#vimMakefile%.key:umask77;\#/usr/bin/ope......
  • 分块莫队
    莫队序言其实我不是很赞成把分块和莫队放到一起的(可能是我太菜了),原本这周先学的树上合并,树分治扫描线那些的,但是没怎么懂,先写一个记忆最新的吧。简介莫队算法是由莫涛提出的算法,莫队算法可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩展,便能轻松处理树上路径询......
  • 分块学习记录
    Referencelink1hzwer分块9题老年退役选手学点东西之前学过分块但是已经忘得差不多了今天稍微补一补吧。用一道区间最值典题来讲一下。\(1e5\)数列\([l,r]\)最大值。假设数组叫做a长度为\(n\)从一开始标号,那么就可以把这个数组分块每一块的长度是\(\sqrt{n}\)......
  • 乘法逆元 + 扩展欧几里得定理/算法
    数学之乘法逆元Part1:逆元是什么一个东西的逆元,就是指在一种运算/操作下能够抵消这个东西所带来影响的东东举个例子4的加法逆元就是-4​ 2在普通乘法中的逆元就是\(2^{-1}\)而乘法逆元指的是在模意义下的乘法逆元设原式为​\(1*a\equiva\modp\)那么......
  • 基于Python语言快速批量运行DSSAT模型及交叉融合、扩展
    随着数字农业和智慧农业的发展,基于过程的作物生长模型(Process-basedCropGrowthSimulationModel)在模拟作物对气候变化的响应与适应、农田管理优化、作物品种和株型筛选、农业碳中和、农田固碳减排等领域扮演着越来越重要的作用。DecisionSupportSystemsforAgrotechnolog......
  • Flink系列-SQL connector扩展以及DataGenTableSourceFactory源码走读
    一、说明    通常我们直接使用Flink的sql进行实时任务开发,经常会遇到扩展新的数据源端或者目标端的场景,或者需要了解connector的一些源码机制,方便开发和定位问题。    如何扩展新增Sqlconnector呢?扩展ApacheFlink的新SQLConnector主要涉及以下几个步骤:......