首页 > 其他分享 >数论分块

数论分块

时间:2022-12-04 11:55:11浏览次数:65  
标签:lfloor frac 分块 数论 sqrt rfloor 我们

数论分块

首先我们需要知道数论分块的用途:它可以快速计算含有除法向下取整的和式。形如\(\sum_{i=1}^{n}f(i)g(\lfloor{\frac{n}{i}}\rfloor)\).为什么可以快速计算呢,因为那个g的部分我们可以采用分块的思想快速求解。也就是就\(O(\sqrt{n})\)的时间复杂度里面求解。

下面讲解为什么是这样的:

因为\(\lfloor{\frac{n}{i}}\rfloor\)的值是一个块状分布,就是所有的值聚集在一个连续的快里面。例如:n=21时,我们按照\(\lfloor{\frac{21}{i}}\rfloor\)的值不同,可以把i的值域分为8块:{1},{2},{3},{4},{5},{6,7},{8,9,10}.{11,12,13,\(\cdots,21\)}.

这里我们可以根据图像进行理解:

证明1:分块的快数需要\(\leq2 \lfloor{\sqrt{n}}\rfloor\)

当我们的\(i\leq\lfloor{\sqrt{n}}\rfloor\),\(\lfloor{\frac{n}{i}}\rfloor\)有\(\lfloor{\sqrt{n}}\rfloor\)种取值。这里我们可以这么记忆,也就是i从\(1\sim \sqrt{n}\)有多少种不同的取值。然后下取整一下就好了。

当\(i\ge\sqrt{n}\)时,\(\lfloor{\frac{n}{i}}\rfloor \leq \lfloor{\sqrt{n}},所以\lfloor{\frac{n}{i}}\rfloor最多有根号n种取值。\)

证明2:i所在块的右端点是\(\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\rfloor\)

一定要注意这个k是指i所在块的值,也就是函数的纵坐标.


例题讲解

[题目链接]([CQOI2007]余数求和 - 洛谷)

核心思路:首先我们应该对于k mod i 进行化简。\(k\pmod{i}=k-(k/i)*i\).然后我们会惊奇的发现后面那一部分就是我们刚开始的求和公式。然后我们就可以采用在\(\sqrt{n}\)的时间复杂度求出来\(t=\lfloor{\frac{k}{i}}\rfloor\).

具体的思路是我们可以利用t在这个\([L,R]\)这个区间里面的分块值不变,注意我们的L和R是已经在一个块里面的。然后我们在不断地迭代更新L和R,因为我们的R是可以通过数论分块的公式求出来的,所以我们可以L=R+1来迭代更新.

\(对于\sum_{i=1}^{r}i\)这个求和就是很容易的了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 110, M = 11, MOD = 1e8;

int main()
{
	LL n, k;
	cin >> n >> k;
	LL res = n * k;
	LL l = 1,r;
	while (l <= n)
	{
		if (k / l)
			r = min(k / (k / l), n);
		else//因为一旦k/l等于0就说明这个l已经很大了.所以k/(k/l)就是一个无穷的数了,但是我们右端点最大都是不可以超过n的
			r = n;
		res -= (k / l) * (r - l + 1) * (l + r) / 2;
		l = r + 1;//迭代更新
	}
	cout << res << endl;

}

标签:lfloor,frac,分块,数论,sqrt,rfloor,我们
From: https://www.cnblogs.com/xyh-hnust666/p/16949595.html

相关文章

  • BZOJ 4833 最小公倍佩尔数 题解 (数论,推式子)
    题目链接神奇数论题。做这题需要知道两个结论:对于满足\(f_{i+2}=a\cdotf_{i+1}+b\cdotf_{i}\),也就是形式类似斐波那契数列的序列,有\(gcd(f_i,f_j)=f_{gcd(i,j)}\)(据......
  • 分块指北
    分块思想最根本的部分是“平衡”二字。以下例题大致按难度排序,但可能有并列当前版本是大纲,关于题目的分析很可能并不完善。以及介绍部分可能也不全面/完善,如有疏漏敬请......
  • 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\]式子的一......
  • 【数论】约数
    文章目录​​一、试除法求n的所有约数​​​​二、约数个数​​​​三、约数之和​​​​四、最大公约数(欧几里得算法/辗转相除法)​​一、试除法求n的所有约数vector<int>g......
  • 2021 陕西省赛 C - GCD // 整除分块
    题目来源:2021年ICPC国际大学生程序设计竞赛暨陕西省第九届大学生程序设计竞赛题目链接:https://ac.nowcoder.com/acm/contest/35232/C题意给定三个整数\(l\)、\(r\)、\(......
  • 关于基础数论之同余定理
    数论中的重要概念。给定一个正整数m,如果两个整数a和b满足a-b能够被m整除,即(a-b)/m得到一个整数,那么就称整数a与b对模m同余,记作a≡b(modm)。对模m同余是整数的一个等价关......
  • 分块快速入门
    基本思想有一句老话,叫“大段维护,局部朴素”。其实就是将一些东西人为的分为若干块,然后每个块整体的维护一些东西,小范围内直接暴力做,做到时空平衡。其实和根号分治有点像......
  • 【UOJ771】【UER11】科考工作(数论,构造)
    题意:给定质数\(p\)和\(2p-1\)个数\(a_1,\cdots,a_{2p-1}\),从中选出\(p\)个数使得它们模\(p\)意义下的和为\(0\),要求给出构造。\(p\leq3\times10^5\)。题解:......
  • 数论分块
    数论分块对于含有除法向下取整的式子,可以使用数论分块,将\(\left\lfloor\frac{n}{i}\right\rfloor\)相同的数统一计算。使式子\(\left\lfloor\frac{n}{i}\right......