首页 > 其他分享 >整除分块

整除分块

时间:2022-12-19 13:56:55浏览次数:35  
标签:lfloor mathbb right frac 分块 rfloor 整除 left

符号约定

\(\left\lfloor x\right\rfloor\):\(x\)下取整。
\(\left\{x\right\}\):\(x\)的小数部分。
显然,对于\(\forall x\ge 0,x\in\mathbb{Q}\),有\(x=\left\lfloor x \right\rfloor+\left\{x\right\}\)
\(\left|V\right|\):集合\(V\)的元素个数,称为集合的阶。

引理证明

引理\(1\):

\(\forall a,b,c\in\mathbb{Z},\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor\)
证明:
\(\because\frac{a}{b}=\left\lfloor\frac{a}{b}\right\rfloor+\left\{\frac{a}{b}\right\}\)
\(\therefore \left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{a}{b}\cdot \frac{1}{c}\right\rfloor=\left\lfloor\left(\left\lfloor\frac{a}{b}\right\rfloor+\left\{\frac{a}{b}\right\}\right)\cdot \frac{1}{c}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}+\frac{\left\{\frac{a}{b}\right\}}{c}\right\rfloor\)
\(\because 0\le \left\{\frac{a}{b}\right\}<1,0\le\left\{\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\}<1\)
\(\therefore \left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor\)

引理\(2\):

\(\forall n\in\mathbb{N_{+}},\left|\left\{\left\lfloor\frac{n}{d}\right\rfloor\mid d\in\mathbb{N_{+}},d\le n\right\}\right|\le\left\lfloor2\sqrt{n}\right\rfloor\)

标签:lfloor,mathbb,right,frac,分块,rfloor,整除,left
From: https://www.cnblogs.com/jd122/p/16991956.html

相关文章

  • 分块内存映射处理大文件-例子
    内存映射文件可以用于3个不同的目的•系统使用内存映射文件,以便加载和执行.exe和DLL文件。这可以大大节省页文件空间和应用程序启动运行所需的时间。•可以使用内存映射......
  • 分块入门
    分块入门1.数列分块入门1模板:LOJ#6277数列分块入门1题目:给定一个长度为\(n\)的数组\(a\)和\(m\)次操作,要求支持区间加法和单点查询。\(1\len,m\le5\times......
  • 分块杂写
    大概会持续更新?似乎是配套分块指北的呢!很多题都没代码(最初分块区间\(x\)改成\(y\)的操作有个trick。我们将序列分块,每块在值域上维护一个并查集,将所有值为\(x\)......
  • 【DSY】直线 题解(平面分块)
    Link.平面分块。Solution直接观察题面可以发现,这道题实在没有什么高深的技巧性可言。于是我们直接暴力:分块。然后wjy大佬表示,这个做法有着二维线段树的思想。下面......
  • 数论分块
    数论分块首先我们需要知道数论分块的用途:它可以快速计算含有除法向下取整的和式。形如\(\sum_{i=1}^{n}f(i)g(\lfloor{\frac{n}{i}}\rfloor)\).为什么可以快速计算呢,因为......
  • 分块指北
    分块思想最根本的部分是“平衡”二字。以下例题大致按难度排序,但可能有并列当前版本是大纲,关于题目的分析很可能并不完善。以及介绍部分可能也不全面/完善,如有疏漏敬请......
  • layui upload 分块上传实现
    由于项目需要上传超大文件,当然现在的条件好了,1-3百M的文件没多大问题,但是超过1G的还是有问题的。(当然oss单个文件最高可以5g)对于大额文件上传存在上传缓慢甚至失败的问题......
  • 数论分块
    数论分块数论分块也叫整除分块是用于快速处理类似于\[\sum_{i=1}^n\lceil\frac{n}{i}\rceil\text{或者}\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor\]式子的一......
  • 2021 陕西省赛 C - GCD // 整除分块
    题目来源:2021年ICPC国际大学生程序设计竞赛暨陕西省第九届大学生程序设计竞赛题目链接:https://ac.nowcoder.com/acm/contest/35232/C题意给定三个整数\(l\)、\(r\)、\(......
  • 下面是用筛选法求100之内的素数,其实原理和上一个差不多,只是这里用到了数组以及不是用
    #include<stdio.h>#include<math.h>intmain(){inti,j,n,a[101];for(i=1;i<=100;i++){a[i]=i;}a[1]=0;for(i=2;i<sqrtf(100);i++){for(j=i+1;j<=100;j++){if(a[i]!=0&......