当前位置: 首页 > news >正文

数论分块

本质就是利用取整分数值的块状分布。

UVA11526 H(n)

题意: ∑ i = 1 n n i \sum_{i=1}^{n} \frac {n}{i} i=1nin

解析:

⌊ n i ⌋ \lfloor \frac{n}{i} \rfloor in 只有 O ( n ) O(\sqrt n) O(n ) 种取值,考虑将相同值同时处理。时间复杂度 O ( T n ) O(T\sqrt n) O(Tn )

对于 i i i,其块右端点 j j j 满足: j = ⌊ n ⌊ n i ⌋ ⌋ j = \lfloor \dfrac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor j=inn

证明:对所有 ⌊ n i ⌋ = k \lfloor \frac{n}{i} \rfloor=k in=k i i i:由 k ≤ n i k \le \frac{n}{i} kin,有 ⌊ n k ⌋ ≥ ⌊ n n i ⌋ = ⌊ i ⌋ = i \lfloor\frac{n}{k}\rfloor \ge \lfloor {\frac{n}{\frac n i}} \rfloor= \lfloor i \rfloor = i kninn=i=i

⌊ n k ⌋ \lfloor\frac{n}{k}\rfloor kn ⌊ n ⌊ n i ⌋ ⌋ \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor inn 即为该块所在右端点。

代码

[AHOI2005] 约数研究

考虑约数 i i i 1 ∼ n 1 \sim n 1n 中出现次数,即 i i i 的倍数个数,为 n i \frac{n}{i} in。答案即为 ∑ i = 1 n ⌊ n i ⌋ \sum_{i=1}^{n} \lfloor{\frac{n}{i}}\rfloor i=1nin

时间复杂度 O ( n ) O(\sqrt n) O(n )

代码

约数和

同样考虑约数的贡献,即求 ∑ i = 1 n i × ⌊ n i ⌋ \sum_{i=1}^{n} i \times \lfloor\frac{n}{i}\rfloor i=1ni×in

考虑到原式子 < ∑ i = 1 n n < \sum_{i=1}^n n <i=1nnlong long 即可。

时间复杂度 O ( n ) O(\sqrt n) O(n )

代码

[CQOI2007] 余数求和

∑ i = 1 n k m o d i = ∑ i = 1 n ( k − ⌊ k i ⌋ i ) = n k − ∑ i = 1 n ⌊ k i ⌋ i \sum_{i=1}^n k \bmod i \\ =\sum_{i=1}^n (k - \lfloor{\frac{k}{i}}\rfloor i) \\ =nk-\sum_{i=1}^n \lfloor{\frac{k}{i}}\rfloor i i=1nkmodi=i=1n(kiki)=nki=1niki

枚举到 k k k 即可, n , k n,k n,k 同阶时时间复杂度 O ( n ) O(\sqrt n) O(n )

CF1485C Floor and Mod

妙。

法一

⌊ a b ⌋ = a m o d b \lfloor \frac{a}{b} \rfloor = a\bmod b ba=amodb

⌊ a b ⌋ = a − ⌊ a b ⌋ b \lfloor \frac{a}{b} \rfloor = a - \lfloor \frac{a}{b} \rfloor b ba=abab

⌊ a b ⌋ = a b + 1 \lfloor \frac{a}{b} \rfloor = \frac{a}{b+1} ba=b+1a

b + 1 ∣ a b+1 \mid a b+1a

⌊ a b ⌋ < b \lfloor \frac{a}{b} \rfloor < b ba<b,得 a < b 2 + b a < b^2+b a<b2+b

b + 1 ∣ a b+1 \mid a b+1a,由 a < b 2 + b a < b^2+b a<b2+b,得 b ∤ a b \nmid a ba,故 ⌊ a b ⌋ = a b + 1 \lfloor \frac{a}{b} \rfloor = \frac{a}{b+1} ba=b+1a

综上, b + 1 ∣ a b+1 \mid a b+1a a < b 2 + b a < b^2 + b a<b2+b 是原命题的一个充要条件。

答案即为
∑ b = 1 y min ⁡ ( x , b 2 + b − 1 ) b + 1 \sum_{b=1}^{y} \dfrac{\min(x,b^2+b-1)}{b+1} b=1yb+1min(x,b2+b1)

分段整除分块即可。

总结:根据整除关系、范围得到一些性质,从而找出充要条件。

代码

法二(官方做法)

⌊ a b ⌋ = a m o d b = k \lfloor \frac{a}{b} \rfloor = a\bmod b = k ba=amodb=k

a = k b + k a = kb + k a=kb+k

b + 1 = a k b+1=\frac{a}{k} b+1=ka

k < b k < b k<b,得 k + 1 < a k k+1<\frac a k k+1<ka,故 k k k 为根号级别。

枚举 k k k,考虑 b b b 的数量。可得 b ≤ x k − 1 b \le \frac x k - 1 bkx1,且 k < b ≤ y k < b \le y k<by

总结:观察 + 放缩 k k k 的范围。

代码

相关文章:

数论分块

本质就是利用取整分数值的块状分布。 UVA11526 H(n) 题意&#xff1a; 求 ∑ i 1 n n i \sum_{i1}^{n} \frac {n}{i} ∑i1n​in​。 解析&#xff1a; ⌊ n i ⌋ \lfloor \frac{n}{i} \rfloor ⌊in​⌋ 只有 O ( n ) O(\sqrt n) O(n ​) 种取值&#xff0c;考虑将相同值同…...

宏任务与微任务,代码执行顺序

js引擎工作进程是同步的。事件循环机制&#xff0c;事件队列。 脚本代码执行顺序&#xff0c;是先执行同步代码&#xff0c;遇到微任务&#xff0c;就把它推进任务队列中。每个宏任务完成后&#xff0c;再执行下一个宏任务。 宏任务有哪些&#xff1a; i/o读写 定时器setTi…...

正方形(Squares, ACM/ICPC World Finals 1990, UVa201)rust解法

有n行n列&#xff08;2≤n≤9&#xff09;的小黑点&#xff0c;还有m条线段连接其中的一些黑点。统计这些线段连成了多少个正方形&#xff08;每种边长分别统计&#xff09;。 行从上到下编号为1&#xff5e;n&#xff0c;列从左到右编号为1&#xff5e;n。边用H i j和V i j表示…...

【算法设计与分析qwl】伪码——顺序检索,插入排序

伪代码&#xff1a; 例子&#xff1a; 改进的顺序检索 Search(L,x)输入&#xff1a;数组L[1...n]&#xff0c;元素从小到大排序&#xff0c;数x输出&#xff1a;若x在L中&#xff0c;输出x位置下标 j ,否则输出0 j <- 1 while j<n and x>L[j] do j <- j1 if x<…...

Uniapp路由拦截-自定义路由白名单

步骤一:新建routerIntercept.js文件 步骤二:routerIntercept文件中写入:(根据自己需要修改whiteList白名单中的页面路径和自己的逻辑处理) import Vue from vue // 白名单 const whiteList = [/pages/public/login,/pages/public/privacyAgreement, ]export default asy…...

在中国可以使用 HubSpot 吗?

当谈到市场营销和客户关系管理工具时&#xff0c;HubSpot通常是一家企业的首选。然而&#xff0c;对于许多中国的企业来说&#xff0c;一个重要的问题是&#xff1a;在中国可以使用HubSpot吗&#xff1f;这个问题涉及到不同的方面&#xff0c;包括政策法规、社交媒体平台、语言…...

Java的基础应用

Java是一种广泛应用于软件开发的编程语言&#xff0c;基础应用涵盖了很多方面。以下是Java的一些基础应用方面的介绍&#xff1a; 1. 控制流语句&#xff1a;Java中的程序流程控制语句分为选择语句和循环语句。选择语句包括if-else语句和switch语句&#xff0c;循环语句包括fo…...

【excel】列转行

列转行 工作中有一些数据是列表&#xff0c;现在需要转行 选表格内容&#xff1a;在excel表格中选中表格数据区域。点击复制&#xff1a;在选中表格区域处右击点击复制。点击选择性粘贴&#xff1a;在表格中鼠标右击点击选择性粘贴。勾选转置&#xff1a;在选择性粘勾选转置选…...

用Bing绘制「V我50」漫画;GPT-5业内交流笔记;LLM大佬的跳槽建议;Stable Diffusion生态全盘点第一课 | ShowMeAI日报

&#x1f440;日报&周刊合集 | &#x1f3a1;生产力工具与行业应用大全 | &#x1f9e1; 点赞关注评论拜托啦&#xff01; &#x1f525; 美国升级AI芯片出口禁令&#xff0c;13家中国GPU企业被列入实体清单 nytimes.com/2023/10/05/technology/chip-makers-china-lobbying…...

Java身份证实名认证-阿里云API 【姓名、身份证号】

1. 阿里云API市场 https://market.aliyun.com/products/57126001/cmapi00053442.html?spm5176.2020520132.101.3.a6217218nxxEiy#skuyuncode47442000022 购买对应套餐 2. 复制AppCode https://market.console.aliyun.com/imageconsole/index.htm#/?_kl85e10 云市场-已购买服…...

ND协议——无状态地址自动配置 (SLAAC)

参考学习&#xff1a;计算机网络 | 思科网络 | 无状态地址自动配置 (SLAAC) | 什么是SLAAC_瘦弱的皮卡丘的博客-CSDN博客 与 IPv4 类似&#xff0c;可以手动或动态配置 IPv6 全局单播地址。但是&#xff0c;动态分配 IPv6 全局单播地址有两种方法&#xff1a; 如图所示&#…...

iOS开发UITableView的使用,区别Plain模式和Grouped模式

简单赘述一下 的创建步骤 // 创建UITableView self.tableView [[UITableView alloc] initWithFrame:self.view.bounds style:UITableViewStylePlain]; // 设置数据源和代理 self.tableView.dataSource self; self.tableView.delegate self; // 注册自定义UITableViewCe…...

css美化滚动条

/*定义滚动条高宽及背景 高宽分别对应横竖滚动条的尺寸*/ ::-webkit-scrollbar { width: 8px; height: 8px; background-color: rgba(0,0,0,.2); } /*定义滚动条轨道 内阴影圆角*/ ::-webkit-scrollbar-track { -webkit-box…...

【CANoe】XML Test Module使用实例

文章目录 一、实操步骤1、增加XML Test Module节点2、配置XML Test Module节点3、XML Test Module节点增加CAPL脚本(.can文件)4、文件夹结构5、使用仿真节点开始测试6、测试结果与测试报告7、同理&#xff0c;在Test Setup也可如此操作 一、实操步骤 1、增加XML Test Module节…...

oracle的update语句where条件后的索引字段为空时不执行

问题描述&#xff1a; update 表名 set age ‘23’ where id1 and name‘lili’; 当在oracle执行以上sql时执行成功&#xff0c;但是当传入的name为null时&#xff0c;sql不成立。我的表中id和name是联合唯一索引&#xff0c;以为name不会为空&#xff0c;但实际上name可以为空…...

RabbitMQ的特点

RabbitMQ是一个开源的消息中间件&#xff0c;用于在不同的应用程序之间进行异步通信。它支持多种消息传递协议&#xff0c;如AMQP、MQTT、STOMP等。 RabbitMQ具有以下特点&#xff1a; 可扩展性&#xff1a;RabbitMQ可以通过添加更多的节点和队列来实现水平扩展。 可靠性&…...

JS单选框默认选中样式修改,为白色背景中心有黑色小圆点的样式

要修改JavaScript中默认选中的单选框的样式为白色背景并带有黑色小圆点&#xff0c;你可以使用CSS来实现。以下是一个示例&#xff0c;展示如何修改样式&#xff1a; <style>/* 修改默认选中单选框的样式 */input[type"radio"]:checked {appearance: none; /*…...

2023年下半年NPDP考试今天开始报名!

2023年第二次NPDP考试将于2023年12月2日&#xff08;周六&#xff09;举行&#xff0c;考试报名相关事项安排如下&#xff1a; 一、考试时间&#xff1a; 12月2日09:00-12:30。 二、报名时间&#xff1a; 10月18日08:00-11月10日23:59。 三、缴费及退考截止时间&#xff1…...

nfs+rpcbind实现服务器之间的文件共享

NFS简介 NFS服务及Network File System&#xff0c;用于在网络上共享存储&#xff0c;分为2,3,4三个版本&#xff0c;最新为4.1版本。NFS基于RPC协议&#xff0c;RPC为Remote Procedure Call的简写。 应用场景&#xff1a;用于A,B,C三台机器上需要保证被访问到的文件是一样…...

10-k8s-身份认证与鉴权

文章目录 一、ServiceAccount介绍二、ServiceAccount相关的资源对象三、dashboard空间示例 一、ServiceAccount介绍 ServiceAccount&#xff08;服务账户&#xff09;概念介绍 1&#xff09;ServiceAccount是Kubernetes集群中的一种资源对象&#xff0c;用于为Pod或其他资源提供…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...