数论与线性代数——整除分块【数论分块】的【运用】【思考】【讲解】【证明(作者自己证的QWQ)】

文章目录

    • 整除分块的思考与运用
    • 整除分块的时间复杂度证明 & 分块数量
    • 整除分块的公式 & 公式证明
      • 公式证明
    • 代码code↓

整除分块的思考与运用

整除分块是为了解决一个整数求和问题


题目的问题为: ∑ i = 1 n ⌊ n i ⌋ \sum_{i=1}^{n} \left \lfloor \frac{n}{i} \right \rfloor i=1nin

求出上述式子的值为多少?

上述问题等同于 c o d e code code

int sum=0;
for(int i=1;i<=n;i++) sum+=n/i;//int是整除类型,所以可以直接整除
return sum;

注意事项: ⌊ x ⌋ \left \lfloor x \right \rfloor x代表不大于 x x x最大整数,也可以成为向下取整


我们不难看出,如果我们直接按题意暴力模拟,则时间复杂度为 O ( n ) O(n) O(n),如果 n n n 比较大就会超时(TLE警告QWQ)

而如果我们将 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor in ( 1 ≤ i ≤ n 1 \le i \le n 1in) 的值输出一下,就会发现其中有许多值是重复的

输出 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor in值的 c o d e code code

for(int i=1;i<=n;i++) cout<<n/i<<endl;

我们可以举例来看一下:

我们令 n = 8 n=8 n=8 ,则有

i i i 的值 i i i = 1 1 1 i i i = 2 2 2 i i i = 3 3 3 i i i = 4 4 4 i i i = 5 5 5 i i i = 6 6 6 i i i = 7 7 7 i i i = 8 8 8
⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor in 的值 8 8 8 4 4 4 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1

此时我们可以明显的看出 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor in 的值被明显的分成了几个块,每个块中的块值相同

分块 [ 1 , 1 ] [1,1] [1,1] [ 2 , 2 ] [2,2] [2,2] [ 3 , 4 ] [3,4] [3,4] [ 5 , 8 ] [5,8] [5,8]
块值 8 8 8 4 4 4 2 2 2 1 1 1

整除分块的时间复杂度证明 & 分块数量

总共需要分少于 2 n 2 \sqrt{n} 2n 种块,证明如下:

i ≤ n i \leq n in 时, n i \frac{n}{i} in 的值有 { n 1 , n 2 , n 3 . . . n n } \left \{ \frac{n}{1} ,\frac{n}{2},\frac{n}{3} ...\frac{n}{\sqrt{n} }\right \} {1n,2n,3n...n n} n i ≥ n \frac{n}{i} \ge \sqrt{n} inn ,共 n \sqrt{n} n 个,此时 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor in n \sqrt{n} n 种取值

i ≥ n i \ge n in 时,有 n i ≤ n \frac{n}{i} \le \sqrt{n} inn ,此时 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor in 也有 n \sqrt{n} n 种取值

两者相加,共 2 n 2 \sqrt{n} 2n 种,所以整除分块的数量为 O ( n ) O(\sqrt{n}) O(n ) 种,所以整除分块的时间复杂度 O ( n ) O(\sqrt{n}) O(n )

整除分块的公式 & 公式证明

结论: R = n ⌊ n L ⌋ R=\frac{n}{\left \lfloor \frac{n}{L} \right \rfloor} R=Lnn
每个块中的元素个数为: ( R − L + 1 ) (R-L+1) (RL+1)

每个块中元素的 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor in 值为 ⌊ n L ⌋ \left \lfloor \frac{n}{L} \right \rfloor Ln

每个块中的和为 a n s = ( R − L + 1 ) × ⌊ n L ⌋ ans=(R-L+1) \times \left \lfloor \frac{n}{L} \right \rfloor ans=(RL+1)×Ln

公式证明

整除分块出现在能被 n n n 完全整除的数之后,到下一个能被 n n n 整除的数之间

令:当前能被 n n n 整除的数为 x x x,下一个能被 n n n 整除的数为 y y y

则有,整除分块的区间为 [ ( x + 1 ) ∼ y ] [(x+1) \sim y] [(x+1)y]

令: L = x + 1 L=x+1 L=x+1 R = y R=y R=y v a l u e value value为分块区间的值,则有,
v a l u e = ⌊ n x + 1 ⌋ = ⌊ n L ⌋ value =\left \lfloor \frac{n}{x+1} \right \rfloor=\left \lfloor \frac{n}{L} \right \rfloor value=x+1n=Ln
因为, y y y 能被 n n n 完全整除(PS:余数为 0 0 0)

所以, ⌊ n y ⌋ = n y \left \lfloor \frac{n}{y} \right \rfloor= \frac{n}{y} yn=yn,且, n y = v a l u e \frac{n}{y}=value yn=value,则有,
n y = v a l u e \frac{n}{y}=value yn=value y = n v a l u e y= \frac{n}{value} y=valuen

v a l u e = ⌊ n x + 1 ⌋ value =\left \lfloor \frac{n}{x+1} \right \rfloor value=x+1n 代入原式得:
y = n ⌊ n x + 1 ⌋ y= \frac{n}{\left \lfloor \frac{n}{x+1} \right \rfloor} y=x+1nn

我们将 L = x + 1 L=x+1 L=x+1 R = y R=y R=y 代入原式得:
R = n ⌊ n L ⌋ R= \frac{n}{\left \lfloor \frac{n}{L} \right \rfloor} R=Lnn
因为
⌊ n L ⌋ = ⌊ n R ⌋ \left \lfloor \frac{n}{L} \right \rfloor=\left \lfloor \frac{n}{R} \right \rfloor Ln=Rn
且因为 ⌊ n R ⌋ = n R \left \lfloor \frac{n}{R} \right \rfloor= \frac{n}{R} Rn=Rn
因为 ( n / R ) (n/R) (n/R) 能被 n n n 完全整除

所以可以保证 n n n 能完全整除 ⌊ n L ⌋ \left \lfloor \frac{n}{L} \right \rfloor Ln

所以我们可以得证:
⌊ n ⌊ n L ⌋ ⌋ = n ⌊ n L ⌋ {\left \lfloor \frac{n}{{\left \lfloor \frac{n}{L} \right \rfloor}} \right \rfloor}= \frac{n}{\left \lfloor \frac{n}{L} \right \rfloor} Lnn=Lnn

证明完毕


细节详解:

i n t , l o n g l o n g int,long long intlonglong 等整数类型中,可以直接进行整除,所以上面的得证等同于 R = ( n / ( n / L ) ) R=(n/(n/L)) R=(n/(n/L))

代码code↓

#include <bits/stdc++.h>
using namespace std;
long long n,L,R,ans=0;
int main(){cin>>n;for(L=1;L<=n;L=R+1){//L=R+1是代表进入下一个块R=n/(n/L);//公式ans+=(R-L+1)*(n/L);//求和cout<<L<<"~"<<R<<":"<<n/R<<" "<<n/L<<endl;//打印分块情况}cout<<ans;//打印和return 0;
}

n = 8 n=8 n=8 时的运行结果↓:

请添加图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/295283.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

手写三维点云配准的迭代最近点(ICP)算法

在本篇博客中,主要深入研究迭代最近点(ICP)算法,特别是针对三维点云配准的实现。分析一个C++代码片段并解释其关键组成部分。(主要参考高博的ICP算法) 简介 ICP是计算机视觉和机器人领域广泛使用的技术,用于将两组三维点进行配准。其主要应用是将一组观测点与参考模型进…

在idea中使用sql语言提醒

1.Settings中设置 2. 配置好数据库名字 3. altenter 注入方言 注入后是下面这样

Linux:冯·诺依曼结构 OS管理机制

Linux&#xff1a;冯诺依曼结构 & OS管理机制 冯诺依曼结构OS管理机制OS对下层硬件的管理OS对上层用户的服务 冯诺依曼结构 我们常见的计算机&#xff0c;比如笔记本&#xff0c;台式电脑。以及一下不常见的计算机&#xff0c;比如服务器&#xff0c;几乎都遵循冯诺依曼体…

如何理解Java注解反射

Java 8 中文版 - 在线API手册 - 码工具 什么是注解 ◆Annotation是从JDK5.0开始引入的新技术 ◆Annotation的作用: 不是程序本身&#xff0c;可以对程序作出解释.(这一点和注释(comment)没什么区别) 可以被其他程序(比如:编译器等)读取 Annotation的格式: > 注解是以&quo…

redis 的StringRedisTemplate

6.3 StringRedisTemplate 尽管JSON的序列化方式可以满足我们的需求&#xff0c;但依然存在一些问题&#xff0c;如图&#xff1a; 为了在反序列化时知道对象的类型&#xff0c;JSON序列化器会将类的class类型写入json结果中&#xff0c;存入Redis&#xff0c;会带来额外的内存…

ES8 学习 -- async 和 await / 对象方法扩展 / 字符串填充

文章目录 1. async 和 await1.1 基本语法1.2 使用示例1.3 案例练习 2. 对象方法扩展2.1 Object.values(obj)2.2 Object.entries(obj)2.3 Object.getOwnPropertyDescriptors(obj)使用示例 3. 字符串填充4. 函数参数的末尾加逗号 1. async 和 await async 函数&#xff0c;使得异…

JavaScript 设计模式之代理模式

代理模式&#xff0c;代理&#xff08;proxy&#xff09;是一个对象&#xff0c;它可以用来控制对另一个对象的访问。 现在页面上有一个香港回归最想听的金典曲目列表&#xff1a; <ul id"container"><li>我的中国心</li><li>东方之珠<…

Photoshop 2024 Mac/win---图像处理的新纪元,解锁无限创意

Photoshop 2024是一款功能强大的图像处理软件&#xff0c;以其卓越的性能和广泛的应用领域&#xff0c;赢得了设计师、摄影师、图形艺术家等各类创意工作者的青睐。它提供了丰富的绘画和编辑工具&#xff0c;让用户能够轻松进行图片编辑、合成、校色、抠图等操作&#xff0c;实…

Redis缓存设计与性能优化【缓存和数据库不一致问题,解决方案:1.加过期时间这样可以一段时间后自动刷新 2.分布式的读写锁】

Redis缓存设计与性能优化 缓存与数据库双写不一致 缓存与数据库双写不一致 在大并发下&#xff0c;同时操作数据库与缓存会存在数据不一致性问题 1、双写不一致情况 2、读写并发不一致 解决方案&#xff1a; 1、对于并发几率很小的数据(如个人维度的订单数据、用户数据等)&a…

LabelConvert: 目标检测和图像分割数据集格式转换工具

LabelConvert LabelConvert是一个目标检测和图像分割的数据集格式转换工具&#xff0c;支持labelme、labelImg与YOLO、VOC和COCO 数据集格式之间的相互转换。 支持的转换格式 安装 pip install label_convert具体使用方法 由于文章篇幅所限&#xff0c;请移步LabelConvert官…

算法学习——LeetCode力扣动态规划篇8(300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组、1143. 最长公共子序列)

算法学习——LeetCode力扣动态规划篇8 300. 最长递增子序列 300. 最长递增子序列 - 力扣&#xff08;LeetCode&#xff09; 描述 给你一个整数数组 nums &#xff0c;找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列&#xff0c;删除&#xff08;或不删…

Flutter开发之图片选择器

使用FLutter开发了一个图片选择的组件&#xff0c;功能如下&#xff1a; 1、支持设置最大可选图片的个数&#xff1b; 2、根据选择的图片个数自适应容器组件的高度&#xff1b; 3、可设置容器的最大高度&#xff1b; 4、支持点击放大和删除功能&#xff1b; 具体效果如下 …

Java多线程实战-从零手搓一个简易线程池(三)线程工厂,核心线程与非核心线程逻辑实现

&#x1f3f7;️个人主页&#xff1a;牵着猫散步的鼠鼠 &#x1f3f7;️系列专栏&#xff1a;Java全栈-专栏 &#x1f3f7;️本系列源码仓库&#xff1a;多线程并发编程学习的多个代码片段(github) &#x1f3f7;️个人学习笔记&#xff0c;若有缺误&#xff0c;欢迎评论区指正…

漂亮哇塞的可视化大屏页面该如何设计?

要提升可视化界面的设计美观度&#xff0c;可以从以下几个方面入手&#xff1a; 使用高质量的图片和素材&#xff1a;使用高质量的图片和素材可以让界面更加美观。可以选择高清晰度的图片和素材&#xff0c;使得整个界面的质感更加高端。突出重点&#xff1a;在界面设计中&…

《QT实用小工具·八》数据库通用翻页类

1、概述 源码放在文章末尾 该项目实现数据库通用翻页类&#xff0c;主要包含如下功能&#xff1a; 1:自动按照设定的每页多少行数据分页 2:只需要传入表名/字段集合/每页行数/翻页指示按钮/文字指示标签 3:提供公共静态方法绑定字段数据到下拉框 4:建议条件字段用数字类型的主…

debian的使用笔记

1. XP风格任务栏 安装 debian-live-12.5.0-amd64-xfce.iso 后&#xff0c;把下面的任务栏删除&#xff0c;把上面的任务栏移到下面&#xff0c;然后设置如下选项 2. 命令自动补全 sudo apt install bash-completion 3. 找不到命令 sudo apt install command-not-found sudo…

RISC-V GNU Toolchain 工具链安装问题解决(含 stdio.h 问题解决)

我的安装过程主要参照 riscv-collab/riscv-gnu-toolchain 的官方 Readme 和这位佬的博客&#xff1a;RSIC-V工具链介绍及其安装教程 - 风正豪 &#xff08;大佬的博客写的非常详细&#xff0c;唯一不足就是 sudo make linux -jxx 是全部小写。&#xff09; 工具链前前后后我装了…

论文阅读RangeDet: In Defense of Range View for LiDAR-based 3D Object Detection

文章目录 RangeDet: In Defense of Range View for LiDAR-based 3D Object Detection问题笛卡尔坐标结构图Meta-Kernel Convolution RangeDet: In Defense of Range View for LiDAR-based 3D Object Detection 论文&#xff1a;https://arxiv.org/pdf/2103.10039.pdf 代码&…

栈溢出攻击的软硬件缓解技术

为了防范栈溢出攻击&#xff0c;现代处理器架构&#xff08;如Arm架构&#xff09;具有执行权限。在Armv8-A中&#xff0c;主要的控制是在MMU地址转换表&#xff08;translation tables&#xff09;中的执行权限位。 UXN User (EL0) Execute-never …

SpringBoot+thymeleaf完成视频记忆播放功能

一、背景 1)客户要做一个视频播放功能,要求是系统能够记录观看人员在看视频时能够记录看到了哪个位置,在下次观看视频的时候能够从该位置进行播放。 2)同时,也要能够记录是谁看了视频,看了百分之多少。 说明:由于时间关系和篇幅原因,我们这里只先讨论第一个要求,第…