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

整除分块

时间:2024-07-22 20:11:08浏览次数:13  
标签:lfloor right 分块 dfrac sum rfloor 整除 left

整除分块

为什么放在 \(9.\) 这个板块捏?

感觉前面很多地方都会 浅浅涉及

建议阅读 数论函数基础 章节,了解基本概念与先要知识


又称 数论分块,因其解决的问题 与整除密切相关 而得名,常用于求解形如

\[\begin {aligned} \sum _ {i = 1} ^ n { f (i) g \left ( \left \lfloor \dfrac n i \right \rfloor \right ) } \end {aligned} \]

这样的 和式,必要前提是 \(f\) 的 前缀和 可以快速计算,或 已经得出


此处获取本节调试数据 / 代码包

全文 绝大多数 内容是对 [0] 中讲述的 粗略抄写胡乱加工


1. 原理

容易证明,不同的 \(\left \lfloor \dfrac n i \right \rfloor\) 的取值只有至多 \(2 \sqrt n\) 个

当 \(i \le \sqrt n\) 时,至多 \(\sqrt n\) 种 不同取值

当 \(i > \sqrt n\) 时,\(\dfrac n i < \sqrt n\),同样至多 \(\sqrt n\) 种 不同取值

故枚举不同取值,乘上 \(f\) 中对应的 一段 就可以得到答案,通常复杂度 \(O (\sqrt n)\)

这样变换后的和式可以表示成 下面的形式

\[\begin {aligned} \sum _ d g (d) \sum _ {i = l} ^ r f (i) \end {aligned} \]

现在 问题的关键 来到了如何 迅速求得 \(l, r\) 的值,即使得 \(\left \lfloor \dfrac n i \right \rfloor = d\) 的 \(i\) 上下界

转化一下,容易发现 \(\left \lfloor \dfrac n i \right \rfloor = d\) 对于 \(i\) 有 \(i (d + 1) > n\) 与 \(id \le n\) 两条限制

于是除过去就变成 \(\left \lfloor \dfrac n {d + 1} \right \rfloor < i \le \left \lfloor \dfrac n d \right \rfloor\),这时候我们设当前枚举到一个 \(l\)

容易计算出其对应的 \(d = \left \lfloor \dfrac n i \right \rfloor\),又根据上文这样的 \(i_{\max} = \left \lfloor \dfrac n d \right \rfloor\),故 \(r = \left \lfloor \dfrac n {\left \lfloor \frac n i \right \rfloor} \right \rfloor\)

当 \(i\) 的 上界不为 \(n\) 时,需要 特殊处理

  • 若上界小于 \(n\) 时,每次 \(r\) 对上界取 \(\min\)
  • 若上界大于 \(n\) 时,\(l\) 大于 \(n\) 之后 \(\left \lfloor \dfrac n i \right \rfloor = 0\)

注意枚举到 \(l > n\) 时退出,不要用 \(r \le n\)


2. 拓展

上取整和式

考虑如果后面的 \(g\) 函数不是 向下取整 的 \(g \left (\left \lfloor \dfrac n i \right \rfloor \right )\) 形式,而是 向上取整 的 \(g \left (\left \lceil \dfrac n i \right \rceil \right )\) 形式呢

我们同样考虑求得 \(i\) 的上下界,\(\left \lceil \dfrac n i \right \rceil = d\) 对于 \(i\) 有 \(id \ge n\) 与 \(i (d - 1) < n\) 两条限制

于是有 \(\left \lceil \dfrac n d \right \rceil \le i < \left \lceil \dfrac n {d - 1} \right \rceil\),同样我们设当前枚举到一个 \(l\)

容易计算出其对应的 \(d = \left \lceil \dfrac n i \right \rceil\),有 \(r < \left \lceil \dfrac n {\left \lceil \frac n i \right \rceil - 1} \right \rceil\),但这还不太行,我们需要 等式形式

稍微变形一下,得到 \(r = \left \lfloor \dfrac {n - 1} {\left \lceil \frac n i \right \rceil - 1} \right \rfloor\) 就行了,注意 \(l= n\) 时 分母为零,需要特判


高维数论分块

当 和式中出现多个上界,形如

\[\begin {aligned} \sum _ {i = 1} ^ n f (i) \sum _ {j = 1} ^ m g \left ( \left \lfloor \dfrac {n_j} i \right \rfloor \right ) \end {aligned} \]

我们每次令

\[\begin {aligned} r = \min _ {j = 1} ^ m \left ( \left \lfloor \dfrac {n_j} { \left \lfloor \frac {n_j} i \right \rfloor } \right \rfloor \right ) \end {aligned} \]

就行了,相当于把 每个 \(n_j\) 的所有断点均取出,故时间复杂度 \(O (\sum \sqrt {n_j})\)


3. 例题

CF1603C Extreme Extension

脑抽抽了,想了好一会儿,看了题解才懂,写的可能很抽象

容易想到 贪心策略,当限制好 \(a_i\) 的大小为 \(v\) 时,那么 \(a_i\) 应当 被分的尽量均匀

形式化的说,此时 \(a_i\) 应当被分为若干个 \(\left \lfloor \dfrac {a_i} {\left \lfloor \frac {a_i} {v} \right \rfloor} \right \rfloor\),余下的数 摊到靠后的几个上

\(\left \lfloor \dfrac {a_i} {\left \lfloor \frac {a_i} {v} \right \rfloor} \right \rfloor\) 就是其 最优情况下分裂出的数的最小值,显然,分裂次数为 \(\left \lceil \dfrac {a_i} v \right \rceil -1\)

显然,一个子段末尾 的值最优的情况是 不被分开

于是根据上述策略,我们可以得到一个 简单的 \(O (n ^ 2)\) 算法,即枚举右端点,向左倒推

显然不够优,仔细思考我们可以发现,对于一个 \(a_i\),\(\left \lfloor \dfrac {a_i} {\left \lfloor \frac {a_i} {v} \right \rfloor} \right \rfloor\) 的取值仅有 \(O (\sqrt n)\) 种

容易证明,对于一个 确定的取值,其 分裂次数是固定的

我们尝试将这些 相同取值的段合并到一起计算贡献

考虑设 \(f _ {i, x}\) 以 \(a_i\) 开头,满足 \(\left \lfloor \dfrac {a_i} {\left \lfloor \frac {a_i} {v} \right \rfloor} \right \rfloor = x\) 的 子串个数(右端点个数),考虑转移

显然,\(a _ {i + 1}\) 的分裂最小取值会 直接决定 转移到的 \(x\),但直接取 分裂最小取值相等 的段 比较困难

\(\left \lfloor \dfrac {a_i} {\left \lfloor \frac {a_i} {v} \right \rfloor} \right \rfloor\) 这个式子的相等段比较难找

故考虑找 分裂出的数个数 \(\left \lceil \dfrac {a_{i}} v \right \rceil\) 相同的段,可以用 向上取整的数论分块 实现

设 \(c = \left \lceil \dfrac {a_i} l \right \rceil\) 表示 分裂出数的个数(\(l\) 即该区间 左端点),那么 \(a_i\) 的分裂最小取值即为 \(\left \lfloor \dfrac {a_i} {c} \right \rfloor\)

于是有 \(f _ {i, v} = \sum _ {j = l} ^ {r} f _ {i + 1, j}\)

注意到 \(f_i, f_{i + 1}\) 中其实均只有 \(O (\sqrt n)\) 个位置有取值,故复杂度可以保证

考虑 \(f_{i, v}\) 的意义,即使得 \(a_i\) 分裂最小取值为 \(v\) 这种情况的 右端点情况数

考虑贡献,显然若 子段左端点 小于等于 \(i\),则 \(f _ {i, v}\) 的 每一种情况 都会被算进去

向左延伸不影响 \(a_i\) 的分裂情况

然后 \(f_{i, v}\) 中每一种情况,都会使得 \(a_i\) 做 \(c - 1\) 次分裂,故其对答案的贡献为 \(i(c - 1) f _ {i, v}\)

于是我们 从右向左转移 即可,每次至多转移 \(O (\sqrt n)\) 个有值点,时间复杂度 \(O (n \sqrt n)\)

注意 \(c = 1\) 时,即 \(a_i\) 不需要分裂

此时 \(f_{i, v} = f _ {i + 1, a_i}\) 再加 \(1\),可以理解为多了一个以 \(a_i\) 开头且仅含这个 \(a_i\) 的子段

代码较为直观(因为很短)上面的讲解很史

#include <bits/stdc++.h>

const int MAXN = 100005;
const int MAXV = 100000;
const int MOD  = 998244353;

using namespace std;

struct Node {
	int val, sum;
};

int N, D, V;
int A[MAXN];
uint32_t Ans = 0;

inline void Solve () {
	std::vector <Node> Now, Lst;
	
	cin >> N, Ans = 0;
	
	for (int i = 1; i <= N; ++ i) cin >> A[i];
	
	Lst.push_back ({A[N], 1});
	
	for (int i = N - 1; i; -- i) {
		while (Now.size ()) Lst.push_back (Now.back ()), Now.pop_back ();
		
		for (int l = 1, r; l <= MAXV; l = r + 1) {
			D = (A[i] - 1) / l + 1, V = (D == 1);
			r = (D > 1) ? (A[i] - 1) / (D - 1) : MAXV;
			
			while (Lst.size () && Lst.back ().val <= r) V = (V + Lst.back ().sum) % MOD, Lst.pop_back ();
			
			Ans += (1ll * i * V % MOD * (D - 1) % MOD), Ans = Ans % MOD;
			Now.push_back ({A[i] / D, V});
		}
	}
	
	Now.clear (), Lst.clear ();
	
	cout << Ans << '\n';
}

int T;

int main () {
	
	cin >> T;
	
	while (T --) Solve ();
	
	return 0;
}


Luogu P2260 [清华集训2012] 模积和

推狮子,先容斥一下把 \(i \neq j\) 的部分搞掉

\[\begin {aligned} & \sum _ {i = 1} ^ n { \sum _ {j = 1} ^ m { \left ( n - \left \lfloor \dfrac n i \right \rfloor i \right ) \left ( m - \left \lfloor \dfrac m j \right \rfloor jj \right ) } } & (i \neq j) \\ =& \sum _ {i = 1} ^ n { \left ( n - \left \lfloor \dfrac n i \right \rfloor i \right ) } \times \sum _ {j = 1} ^ m { \left ( m - \left \lfloor \dfrac m j \right \rfloor j \right ) } & (i \neq j) \\ =& \sum _ {i = 1} ^ n { \left ( n - \left \lfloor \dfrac n i \right \rfloor i \right ) } \times \sum _ {j = 1} ^ m { \left ( m - \left \lfloor \dfrac m j \right \rfloor j \right ) } - \sum _ {i = 1} ^ n { \left ( n - \left \lfloor \dfrac n i \right \rfloor i \right ) \left ( m - \left \lfloor \dfrac m i \right \rfloor i \right ) } \\ =& \left ( n ^ 2 - \sum _ {i = 1} ^ n { \left \lfloor \dfrac n i \right \rfloor i } \right ) \times \left ( m ^ 2 - \sum _ {j = 1} ^ m { \left \lfloor \dfrac m j \right \rfloor j } \right ) - \sum _ {i = 1} ^ n { \left ( n - \left \lfloor \dfrac n i \right \rfloor i \right ) \left ( m - \left \lfloor \dfrac m i \right \rfloor i \right ) } \end {aligned} \]

容易发现 前面两部分 数论分块可以秒掉

后面部分一样的拆开,得到

\[\begin {aligned} & \sum _ {i = 1} ^ n { \left ( n - \left \lfloor \dfrac n i \right \rfloor i \right ) \left ( m - \left \lfloor \dfrac m i \right \rfloor i \right ) } \\ =& \sum _ {i = 1} ^ n { \left ( nm - n \left \lfloor \dfrac m i \right \rfloor i - m \left \lfloor \dfrac n i \right \rfloor i + i ^ 2 \left \lfloor \dfrac n i \right \rfloor \left \lfloor \dfrac m i \right \rfloor \right ) } \\ =& n ^ 2 m - \sum _ {i = 1} ^ n { \left ( n \left \lfloor \dfrac m i \right \rfloor i + m \left \lfloor \dfrac n i \right \rfloor i - i ^ 2 \left \lfloor \dfrac n i \right \rfloor \left \lfloor \dfrac m i \right \rfloor \right ) } \end {aligned} \]

然后再次 整除分块 就可以了,注意这是 二维 的(有 \(n, m\) 两个上界)

#include <stdio.h>
#include <stdint.h>

const uint32_t MAXN = 100005;
const uint32_t MOD  = 19940417;
const uint32_t Inv6 = 3323403;

uint32_t N, M, T;
uint32_t d, v;
uint64_t Ans0, Ans1, Ans2, Ans3, Ans;

inline uint64_t Sum1 (const uint64_t L, const uint64_t R) {
	return ((R * (R + 1) >> 1) - (L * (L + 1) >> 1)) % MOD;
}

inline uint64_t Sum2 (const uint64_t L, const uint64_t R) {
	uint64_t Max = R * (R + 1) % MOD * (2 * R + 1) % MOD * Inv6 % MOD;
	uint64_t Min = L * (L + 1) % MOD * (2 * L + 1) % MOD * Inv6 % MOD;
	return (Max + MOD - Min) % MOD;
}



int main () {
	
	scanf ("%d%d", &N, &M);
	
	if (M < N) T = N, N = M, M = T;
	
	for (uint32_t l = 1, r; l <= N; l = r + 1) 
		r = N / (N / l), d = N / l, Ans1 += Sum1 (l - 1, r) * d % MOD; 
	Ans1 = Ans1 % MOD, Ans1 = 1ull * N * N - Ans1, Ans1 = Ans1 % MOD;
	
	for (uint32_t l = 1, r; l <= M; l = r + 1) 
		r = M / (M / l), d = M / l, Ans2 += Sum1 (l - 1, r) * d % MOD;
	Ans2 = Ans2 % MOD, Ans2 = 1ull * M * M - Ans2, Ans2 = Ans2 % MOD;
	
	
	Ans = Ans1 * Ans2 % MOD, Ans1 = Ans2 = 0;
	
	for (uint32_t l = 1, r; l <= N; l = r + 1) {
		r = (M / (M / l)) < (N / (N / l)) ? (M / (M / l)) : (N / (N / l)), d = N / l, v = M / l;
		Ans1 += Sum1 (l - 1, r) * M % MOD * d, Ans1 = Ans1 % MOD; 
		Ans2 += Sum1 (l - 1, r) * N % MOD * v, Ans2 = Ans2 % MOD;
		Ans3 += Sum2 (l - 1, r) * d % MOD * v, Ans3 = Ans3 % MOD;
	}
	
	Ans0 = ((1ull * N * N % MOD * M % MOD) + MOD - Ans1 + MOD - Ans2 + Ans3) % MOD;
	
	printf ("%llu\n", (Ans + MOD - Ans0) % MOD);
	
	return 0;
}

Luogu P3579 [POI2014] PAN-Solar Panels

考虑性质,若 \((a, b]\) 中存在 \(x\) 的 整倍数,则一定有 \(\left \lfloor \dfrac a x \right \rfloor < \left \lfloor \dfrac b x \right \rfloor\)

容易证明 \(\left \lfloor \dfrac b x \right \rfloor\) 至多 \(O (\sqrt V)\) 种取值

考虑枚举取值,在固定 \(b\),固定 \(\left \lfloor \dfrac b x \right \rfloor\) 时,显然 \(x\) 取值在一个区间 \([l, r]\) 中

显然,\(x\) 越大,\(\left \lfloor \dfrac a x \right \rfloor\) 可能越大,\(\left \lfloor \dfrac a x \right \rfloor < \left \lfloor \dfrac b x \right \rfloor\) 越有可能满足

故满足 \(\left \lfloor \dfrac a x \right \rfloor < \left \lfloor \dfrac b x \right \rfloor\) 等价于在固定 \(\left \lfloor \dfrac b x \right \rfloor\),\(x\) 取值 \([l, r]\) 的情况下,满足 \(\left \lfloor \dfrac a r \right \rfloor < \left \lfloor \dfrac b r \right \rfloor\)

整除分块求解即可,这时候发现有两个区间?二维整除分块 求解即可

#include <stdio.h>
#include <stdint.h>

uint32_t T, a, b, c, d, e;
uint32_t Max;

int main () {
	
	scanf ("%u", &T);
	
	for (uint32_t i = 1; i <= T; ++ i) {
		scanf ("%u%u%u%u", &a, &b, &c, &d);
		Max = 0, -- a, -- c, e = b < d ? b : d;
		for (uint32_t l = 1, r; l <= e; l = r + 1) {
			r = (b / (b / l)) < (d / (d / l)) ? (b / (b / l)) : (d / (d / l));
			if (a / r < b / r && c / r < d / r && r > Max) Max = r;
		}
		printf ("%u\n", Max);
	}
	
	return 0;
}

4. 引用资料

[0] Number Theory —— H_W_Y

标签:lfloor,right,分块,dfrac,sum,rfloor,整除,left
From: https://www.cnblogs.com/FAKUMARER/p/18316772

相关文章

  • 分块入门
    基本思想把一个需要操作的序列分成若干块,分别处理,从而优化时间复杂度。容易证明块长为\(\sqrtn\)时复杂度最优。分块常规单次操作复杂度为\(\mathcal{O}(\sqrtn)\),一般可以当做\(\mathcal{O}(\log^2n)\)来计算复杂度。接下来给几道例题。T1给出一个长为\(n\)的数列......
  • 基于springboot+vue的分块下载文件解决思路
    目录基于fastdfs文件服务nginx+fastdfs启用slice,range进行下载。基于springboot的应用服务器转发nginx服务的文件请求服务。vue使用asyn和await进行请求和合并文件添加进度条一、fastdfs文件服务启动fastdfs服务命令:/usr/bin/fdfs_storaged/etc/fdfs/storage.confstart......
  • LeetCode 2950. 可整除子串的数量
    2950.可整除子串的数量每个英文字母都被映射到一个数字,如下所示。如果字符串的字符的映射值的总和可以被字符串的长度整除,则该字符串是 可整除 的。给定一个字符串 s,请返回 s 的 可整除子串 的数量。子串 是字符串内的一个连续的非空字符序列。示例1:Substrin......
  • 【Python&RS】基于Python分块处理大型遥感影像的方法
    ​    RSer工作时不可避免会用到大型的遥感影像,由于分辨率过高、区域过大、波段信息过多等原因,都会导致数据非常的大。这个时候我们在进行一些简单的操作,如计算NDVI、二值化、分类等时,计算机的内存都会溢出。因此今天跟大家分享一下我平时分块的方法,中间如何计算就按照......
  • LeetCode 974. 和可被 K 整除的子数组
    974.和可被K整除的子数组给定一个整数数组 nums 和一个整数 k ,返回其中元素之和可被 k 整除的非空 子数组 的数目。子数组 是数组中 连续 的部分。示例1:输入:nums=[4,5,0,-2,-3,1],k=5输出:7解释:有7个子数组满足其元素之和可被k=5整除:[4,5,0......
  • 打印100以内所有能被3整除的数,每5个数打印一行(devC++)
     今天让我们来学习如何利用C语言,在运行框中打印100以内所有能被3整除的数,每五个数打印一行。 首先,我们需要定义两个变量,其中n表示1~100的数字,m表示3的倍数的个数。然后利用一个for循环,在循环中n自增,利用一个if判断语句判断是否为3的倍数,如果是,则输出在循环中再利用一个......
  • L1-046 整除光棍(模拟除法)
    这里所谓的“光棍”,并不是指单身汪啦~说的是全部由1组成的数字,比如1、11、111、1111等。传说任何一个光棍都能被一个不以5结尾的奇数整除。比如,111111就可以被13整除。现在,你的程序要读入一个整数x,这个整数一定是奇数并且不以5结尾。然后,经过计算,输出两个数字:第一个数字s,表示......
  • 断点续传:使用java对大文件进行分块与合并
    通常我们下载上传的视频文件比较大。虽然https协议没有规定上传文件大小的限制,但是网络的质量,电脑硬件的参差不齐可能会导致大文件快要上传完成的时候突然断网了要重新上传,非常影响用户体验。以此我们引入了断点续传的功能。什么是断点续传呢?就是我们在上传下载文件的时候,将一个......
  • 欧拉函数、整除分块和扩展欧几里得
    欧拉函数欧拉函数(写作\(\varphi(x)\)),表示\(i\in[1,x]且\gcd(i,x)=1\)的\(i\)的数量。乍一看好像很难求,但我们先考虑最简单的情况,即\(x\in\mathbb{P}\)(\(\mathbb{P}\)表示质数集)的情况。首先很容易看出\(\varphi(x)=x-1\),因为\(x\in\mathbb{P}\),所以\(\foralli......
  • 从 dfs 序求 lca 到虚树到树分块 学习笔记
    前言想象我在口胡三样我都不熟悉的东西并尝试称之为“学习笔记”。其实不过是我自己对于它的一点小理解,甚至可能是错误的!无所谓,口胡!口胡!口胡!口胡!口胡!一些备注\(dfn_u\)为点\(u\)的dfn序,\(nfd_i\)表示第\(i\)个dfs到的点是啥(前者的反数组)dfs序求lca这个很简单,想......