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

news/2024/6/20 21:04:26/文章来源:https://blog.csdn.net/Xeovei/article/details/137233118

文章目录

    • 整除分块的思考与运用
    • 整除分块的时间复杂度证明 & 分块数量
    • 整除分块的公式 & 公式证明
      • 公式证明
    • 代码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.luyixian.cn/news_show_1033572.aspx

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

相关文章

用html实现在页面底部养鱼的效果

<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>在网页底部养鱼</title><link rel"stylesheet" href"./style.css"> </head> <body> <div id"fi…

​ SpringBoot自动装配原理

SpringBoot自动装配原理 SpringBoot的启动类上有一个注解&#xff1a;SpringBootApplication 。该注解是三个注解的复合注解。 1.SpringBootConfiguration 注解 点进SpringBootConfiguration 注解&#xff0c;可以发现其核心注解为Configuration注解&#xff1a; Configuration…

Mysql 常用SQL语句

1、查看mysql中所有的数据库&#xff0c; show databases; 2、创建库 create database 库名;&#xff08;也可以用 create database if not exists 库名; 表示如果库不存在再创建&#xff09; 例&#xff1a;create database if not exists ecology; 3、删除库 …

Mysql数据库故障排查与优化

目录 前言 一、Mysql数据库的单实例故障 1.故障一——拒绝连接数据库 1.1故障内容 1.2问题分析 1.3解决方法 2.故障二——密码错误 2.1故障内容 2.2问题分析 2.3解决方法 3.故障三——数据库处理较慢 3.1故障内容 3.2问题分析 3.3解决方法 4.故障四——数据库表…

【leetcode】力扣简单题两数之和

题目 思路 代码实现 #include<iostream> #include<unordered_map>using namespace std;class Solution { public:vector<int> TwoNumber(const vector<int>& nums, int target){vector<int> number_vector;unordered_map<int, int> …

SpringCloud学习(1)-consul

consul下载安装及使用 1.consul简介 Consul是一种开源的、分布式的服务发现和配置管理工具&#xff0c;能够帮助开发人员构建和管理现代化的分布式系统。它提供了一套完整的功能&#xff0c;包括服务注册与发现、健康检查、KV存储、多数据中心支持等&#xff0c;可以帮助开发人…

代码随想录算法训练营第39天|62.不同路径 |63. 不同路径 II

代码随想录算法训练营第39天|62.不同路径 |63. 不同路径 II 详细布置 62.不同路径 本题大家掌握动态规划的方法就可以。 数论方法 有点非主流&#xff0c;很难想到。 https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html 视频讲解&#xff1a;https…

深入了解C语言中的结构体类型与内存对齐

引言&#xff1a; 在C语言中&#xff0c;结构体是一种自定义的数据类型&#xff0c;它允许我们将不同类型的数据组合在一起&#xff0c;形成一个新的数据类型。结构体的使用为我们解决了一些复杂数据的表示和处理问题&#xff0c;不仅限于单单的整型或者字符。本文将深入探讨结…

网络编程--高并发服务器(二)

这里写目录标题 线程池高并发服务器UDP服务器TCP与UDP机制的对比TCP与UDP优缺点比较UDP的C/S模型实现思路模型分析实现思路&#xff08;对照TCP的C/S模型&#xff09; recvfrom函数、sendto函数 一级目录二级目录二级目录二级目录 一级目录二级目录二级目录二级目录 一级目录二…

C++引用与指针比较

引子&#xff1a; 问题&#xff1a; 指针指向变量必须类型一致&#xff08;int对int*类型指针&#xff09;&#xff0c;这样计算&#xff0c;解引用才能得到正确的结果&#xff0c;那引用也是如此吗&#xff1f; 回答&#xff1a;&#xff08;常引用&#xff09; 从语法来说…

MyBatis主要的类层次结构(Mybatis工具类)

MyBatis主要的类层次结构 每一个MyBatis的应用程序都以一个SqlSessionFactory 对象的实例为核心 。 SqlSessionFactory对象的实例可以通过SqlSessionFactoryBuilder对象来获得 。 SqlSessionFactoryBuilder对象可以从 XML 配置文件中构建 SqlSessionFactory对象。 package…

RN实现全局数据共享(非Redux,使用原生内置的方法实现)

下面这个方法是在RN使用全局数据共享的,使用原生React的方式搞得,相对于Redux配置相对简单,适合小型项目 项目内创建MyContext.js // MyContext.jsimport React from react;const MyContext React.createContext();export default MyContext;App.js引入 // App.jsimport Rea…

【opencv】教程代码 —features2D(7)根据单应性矩阵估计相机坐标系下的物体位姿...

pose_from_homography.cpp从图像中找到棋盘角点并进行姿态估计 从图像中找到棋盘角点并显示 计算角点在世界坐标系中的位置 读取相机内参和畸变系数并校正图像中的角点 计算从3D点到2D点的单应性矩阵 通过奇异值分解(SVD)优化对旋转矩阵的估计 基于单应矩阵分解及其优化结果&am…

HarmonyOS 应用开发之LifecycleForm接口切换LifecycleApp接口切换 LifecycleApp接口切换

LifecycleForm接口切换 FA模型接口Stage模型接口对应d.ts文件Stage模型对应接口onCreate?(want: Want): formBindingData.FormBindingData;ohos.app.form.FormExtensionAbility.d.tsonAddForm(want: Want): formBindingData.FormBindingData;onCastToNormal?(formId: string…

Java复习第十一天学习笔记(IO流),附有道云笔记链接

【有道云笔记】十一 3.27 IO流 https://note.youdao.com/s/PeEdd3Zo 一、IO介绍以及分类 IO: Input Output 流是一组有顺序的&#xff0c;有起点和终点的字节集合&#xff0c;是对数据传输的总称或抽象。即数据在两设备间的传输称为流&#xff0c;流的本质是数据传输&#x…

无人机编队 | 基于自适应航迹评价函数权重的动态窗口法长机-僚机法实现多无人机路径规划附matlab代码

基本概述 实现基于自适应航迹评价函数权重的动态窗口法(Dynamic Window Approach, DWA)的长机-僚机(Leader-Follower)多无人机路径规划是一个复杂的任务,涉及到多个算法的组合与改进。这里我会简要介绍其原理,并提供一个基础的Matlab代码框架,但请注意,这只是一个起点…

如何恢复被.locked勒索病毒加密的服务器和数据库?

.locked勒索病毒有什么特点&#xff1f; .locked勒索病毒的特点主要包括以下几个方面&#xff1a; 文件加密&#xff1a;.locked勒索病毒会对受感染设备上的所有文件进行加密&#xff0c;包括图片、文档、视频和其他各种类型的重要文件。一旦文件被加密&#xff0c;文件的扩展…

Day14_学点CSS_高级选择器Demo

1 后代选择器s1 s2 <!--~ 适度编码益脑&#xff0c;沉迷编码伤身&#xff0c;合理安排时间&#xff0c;享受快乐生活。~ Copyright TangXJ~ Created by TangXJ~ Created&Used date: 2024/3/29 下午3:46 ~ 2024/3/29 下午3:47~ Modified date: 2024/3/29 下午3:47-->…

C语言 | Leetcode C语言题解之3题无重复字符的最长子串

题目&#xff1a; 题解&#xff1a; int lengthOfLongestSubstring(char * s) {//类似于hash的思想//滑动窗口维护int left 0;int right 0;int max 0;int i,j;int len strlen(s);int haveSameChar 0;for(i 0; i < len ; i ){if(left < right){ //检测是否出现重…

OpenHarmony实战开发-图案密码锁组件的使用

介绍 本示例展示了图案密码锁组件的使用&#xff0c;实现了密码设置、验证和重置功能。 图案密码锁组件&#xff1a;以宫格图案的方式输入密码&#xff0c;用于密码验证。手指触碰图案密码锁时开始进入输入状态&#xff0c;手指离开屏幕时结束输入状态并向应用返回输入的密码…