数论分块
本质就是利用取整分数值的块状分布。
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=⌊⌊in⌋n⌋。
证明:对所有 ⌊ n i ⌋ = k \lfloor \frac{n}{i} \rfloor=k ⌊in⌋=k 的 i i i:由 k ≤ n i k \le \frac{n}{i} k≤in,有 ⌊ n k ⌋ ≥ ⌊ n n i ⌋ = ⌊ i ⌋ = i \lfloor\frac{n}{k}\rfloor \ge \lfloor {\frac{n}{\frac n i}} \rfloor= \lfloor i \rfloor = i ⌊kn⌋≥⌊inn⌋=⌊i⌋=i。
故 ⌊ n k ⌋ \lfloor\frac{n}{k}\rfloor ⌊kn⌋ 即 ⌊ n ⌊ n i ⌋ ⌋ \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor ⌊⌊in⌋n⌋ 即为该块所在右端点。
代码
[AHOI2005] 约数研究
考虑约数 i i i 在 1 ∼ n 1 \sim n 1∼n 中出现次数,即 i i i 的倍数个数,为 n i \frac{n}{i} in。答案即为 ∑ i = 1 n ⌊ n i ⌋ \sum_{i=1}^{n} \lfloor{\frac{n}{i}}\rfloor ∑i=1n⌊in⌋。
时间复杂度 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=1nn,long 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=1∑nkmodi=i=1∑n(k−⌊ik⌋i)=nk−i=1∑n⌊ik⌋i
枚举到 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⌋=a−⌊ba⌋b
⌊ 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+1∣a。
由 ⌊ 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+1∣a,由 a < b 2 + b a < b^2+b a<b2+b,得 b ∤ a b \nmid a b∤a,故 ⌊ 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+1∣a 且 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=1∑yb+1min(x,b2+b−1)。
分段整除分块即可。
总结:根据整除关系、范围得到一些性质,从而找出充要条件。
代码
法二(官方做法)
记 ⌊ 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 b≤kx−1,且 k < b ≤ y k < b \le y k<b≤y。
总结:观察 + 放缩 k k k 的范围。
代码
相关文章:
数论分块
本质就是利用取整分数值的块状分布。 UVA11526 H(n) 题意: 求 ∑ i 1 n n i \sum_{i1}^{n} \frac {n}{i} ∑i1nin。 解析: ⌊ n i ⌋ \lfloor \frac{n}{i} \rfloor ⌊in⌋ 只有 O ( n ) O(\sqrt n) O(n ) 种取值,考虑将相同值同…...
宏任务与微任务,代码执行顺序
js引擎工作进程是同步的。事件循环机制,事件队列。 脚本代码执行顺序,是先执行同步代码,遇到微任务,就把它推进任务队列中。每个宏任务完成后,再执行下一个宏任务。 宏任务有哪些: i/o读写 定时器setTi…...
正方形(Squares, ACM/ICPC World Finals 1990, UVa201)rust解法
有n行n列(2≤n≤9)的小黑点,还有m条线段连接其中的一些黑点。统计这些线段连成了多少个正方形(每种边长分别统计)。 行从上到下编号为1~n,列从左到右编号为1~n。边用H i j和V i j表示…...
【算法设计与分析qwl】伪码——顺序检索,插入排序
伪代码: 例子: 改进的顺序检索 Search(L,x)输入:数组L[1...n],元素从小到大排序,数x输出:若x在L中,输出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 吗?
当谈到市场营销和客户关系管理工具时,HubSpot通常是一家企业的首选。然而,对于许多中国的企业来说,一个重要的问题是:在中国可以使用HubSpot吗?这个问题涉及到不同的方面,包括政策法规、社交媒体平台、语言…...
Java的基础应用
Java是一种广泛应用于软件开发的编程语言,基础应用涵盖了很多方面。以下是Java的一些基础应用方面的介绍: 1. 控制流语句:Java中的程序流程控制语句分为选择语句和循环语句。选择语句包括if-else语句和switch语句,循环语句包括fo…...
【excel】列转行
列转行 工作中有一些数据是列表,现在需要转行 选表格内容:在excel表格中选中表格数据区域。点击复制:在选中表格区域处右击点击复制。点击选择性粘贴:在表格中鼠标右击点击选择性粘贴。勾选转置:在选择性粘勾选转置选…...
用Bing绘制「V我50」漫画;GPT-5业内交流笔记;LLM大佬的跳槽建议;Stable Diffusion生态全盘点第一课 | ShowMeAI日报
👀日报&周刊合集 | 🎡生产力工具与行业应用大全 | 🧡 点赞关注评论拜托啦! 🔥 美国升级AI芯片出口禁令,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)
参考学习:计算机网络 | 思科网络 | 无状态地址自动配置 (SLAAC) | 什么是SLAAC_瘦弱的皮卡丘的博客-CSDN博客 与 IPv4 类似,可以手动或动态配置 IPv6 全局单播地址。但是,动态分配 IPv6 全局单播地址有两种方法: 如图所示&#…...
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、同理,在Test Setup也可如此操作 一、实操步骤 1、增加XML Test Module节…...
oracle的update语句where条件后的索引字段为空时不执行
问题描述: update 表名 set age ‘23’ where id1 and name‘lili’; 当在oracle执行以上sql时执行成功,但是当传入的name为null时,sql不成立。我的表中id和name是联合唯一索引,以为name不会为空,但实际上name可以为空…...
RabbitMQ的特点
RabbitMQ是一个开源的消息中间件,用于在不同的应用程序之间进行异步通信。它支持多种消息传递协议,如AMQP、MQTT、STOMP等。 RabbitMQ具有以下特点: 可扩展性:RabbitMQ可以通过添加更多的节点和队列来实现水平扩展。 可靠性&…...
JS单选框默认选中样式修改,为白色背景中心有黑色小圆点的样式
要修改JavaScript中默认选中的单选框的样式为白色背景并带有黑色小圆点,你可以使用CSS来实现。以下是一个示例,展示如何修改样式: <style>/* 修改默认选中单选框的样式 */input[type"radio"]:checked {appearance: none; /*…...
2023年下半年NPDP考试今天开始报名!
2023年第二次NPDP考试将于2023年12月2日(周六)举行,考试报名相关事项安排如下: 一、考试时间: 12月2日09:00-12:30。 二、报名时间: 10月18日08:00-11月10日23:59。 三、缴费及退考截止时间࿱…...
nfs+rpcbind实现服务器之间的文件共享
NFS简介 NFS服务及Network File System,用于在网络上共享存储,分为2,3,4三个版本,最新为4.1版本。NFS基于RPC协议,RPC为Remote Procedure Call的简写。 应用场景:用于A,B,C三台机器上需要保证被访问到的文件是一样…...
10-k8s-身份认证与鉴权
文章目录 一、ServiceAccount介绍二、ServiceAccount相关的资源对象三、dashboard空间示例 一、ServiceAccount介绍 ServiceAccount(服务账户)概念介绍 1)ServiceAccount是Kubernetes集群中的一种资源对象,用于为Pod或其他资源提供…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...
