0.前言

本文为作者放假前の无聊之举……

作者是个菜*，若文章有错误请大佬指正。

食用本文的注意事项如下：

粗体字为重要结论或重要步骤。
给到的例题为作者抽象出来的模型，与原题不同。若作者找到了原题，作者会把原题链接放在下面，方便大家提交。在每一道题的讲解中，原题将称作“原题”，例题将称作“例题”。
若有原题，那么给出的代码为原题的ac代码，若没有原题，给出的代码为例题代码。
划掉的部分为同学评价诋毁或作者~~突发恶疾~~，请自动忽略。
文章中还有一些作者未解决的问题，这样的问题后面会有“请求大佬指点”，若有大佬知道，请在评论区回复。作者会在第一时间送上最高礼节：关注。

1.整除分块の基本问题

求下面式子的值

\sum_{i=1}^{n}\ \lfloor \frac{n}{i} \rfloor

这是原题链接（以下此题称基本问题）

O(n)

暴力很简单，就不给代码了。
这里n是

10^{12}

级别的，

O(n)

肯定会被卡掉，要求给出一个

O(\sqrt{n})

的算法。
这里我们请出整除分块来解决。

2.基本思想&基本定理

我们手算一个原题中的样例

n = 10
i = 1 2 3 4 5 6 7 8 9 10
$\lfloor \frac{n}{i} \rfloor$ = 10 5 3 2 2 1 1 1 1 1

通过样例，我们可以看见当i从1到n变化时，

\lfloor \frac{n}{i} \rfloor

的值在很多连续的i区间内是相同的,有了这个关键性质，我们就可以优化了。

整除分块就是找到这些区间，对每个区间只计算一次 $\lfloor \frac{n}{i} \rfloor$ 的值，然后乘以区间长度。

下面我们来讲讲这个算法的步骤

初始化i=1，结果ans=0；
对于每个i，计算 $k = \lfloor \frac{n}{i} \rfloor$ ；
找到最大的j使得 $\lfloor \frac{n}{j} \rfloor = k$ （也就是块的右端点）。这里，我们隆重请出我们的基本定理：对于 $i \in [1,n]$ ， $\lfloor \frac{n}{i} \rfloor$ 的值会随着i的增大而单调递减，且某些连续区间内的值相同。即 $\lfloor \frac{n}{i} \rfloor=\lfloor \frac{n}{i+1} \rfloor=……=\lfloor \frac{n}{j} \rfloor$ ，其中 $j= \lfloor \frac{n}{k} \rfloor$ 。~~然而作者并不会证明~~；
将 $k\ast(j-i+1)$ 加到结果中;
令 $i=j+1$ ，重复步骤2~5直到 $i>n$ ；

那么很好，通过我们强大的基本定理，我们的复杂度从

O(n) \rarr O(\sqrt{n})

。

下面是大家喜闻乐见的代码环节：

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T,n;
ll getsum(ll x)
{
	ll ans=0;
	for (ll i=1,j;i<=x;i=j+1)
	{
		j=x/(x/i);
		ans+=x/i*(j-i+1);
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>n;
		cout<<getsum(n)<<"\n";
	}
	return 0;
}

3.常见题型

1.例题1

求出下面式子的值：

\sum_{i=1}^{n}\ i*\lfloor \frac{n}{i} \rfloor

~~然而本题我并没有找到原题~~

观察这个式子，发现只比基本问题多乘一个i。那么我们手推一下样例：

n = 10
i = 1 2 3 4 5 6 7 8 9 10
$i*\lfloor \frac{n}{i} \rfloor$ = $\overbrace{10}^{\text{1}}$ $\overbrace{10}^{\text{2}}$ $\overbrace{9}^{\text{3}}$ $\overbrace{8,10}^{\text{4,5}}$ $\overbrace{6,7,8,9,10}^{\text{6,7,8,9,10}}$
sum = 87

~~我贴心地帮你把块分号了~~
通过以上样例我们可以看出，每一个块中都是一个等差数列。 令

q = \lfloor \frac{n}{i} \rfloor

，即基本问题中每一个块中相等的值，其中：

首项 = $i*q$ ;
令 $j = \lfloor \frac{n}{q} \rfloor$ ,即基本问题中块的最后一项，则末项 = $j*q$ ;
项数很简单，是 $j-i+1$ ；
最后，每一个块中的 $sum = q*(i+j)*(j-i+1)/2$ ；

那么，又到了我们喜闻乐见的代码环节：~~其实上面的代码改一下就可以了~~

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T,n;
ll getsum(ll x)
{
	ll ans=0;
	for (ll i=1,j;i<=x;i=j+1)
	{
		ll q=x/i;//改了这里
		j=x/q;
		ans+=q*(i+j)*(j-i+1)/2;//还有这里
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>n;
		cout<<getsum(n)<<"\n";
	}
	return 0;
}

2.例题2

求下面的式子：

\sum_{i=1}^{n}\ k \mod i

这道题有原题呢

如果看出这道题是整除分块，就非常好ban了。那就往整除分块的基本问题上靠，也就是写出带有整除的式子：把

k \mod i

写为

k-i*\lfloor \frac{k}{i} \rfloor

,代入可得

\sum_{i=1}^{n}\ \bigg(k-i*\lfloor \frac{n}{i} \rfloor \bigg)

我们看到了例题1的形式，把求和符号写开，就可以转化为，例1了：

n*k-\sum_{i=1}^{n}\ i*\lfloor \frac{k}{i}\rfloor

这样这道题就做完了，和例1基本类似，不过有一点小问题需要注意一下，k可能小于n，所以

\lfloor \frac{k}{\lfloor \frac{k}{i}\rfloor }\rfloor

可能超过n。（可以手动验证一下）
所以呢，代码要进行一些小小的改动。

又是我们喜闻乐见的代码环节呢~

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,l,r,ans;
int main()
{
	cin>>n>>k;
	ans=n*k;
	for (int l=1;l<=n;l=r+1)
	{
		if (k/l==0) break;
		r=min(k/(k/l),n);// 改下这里
		ans-=(k/l)*(l+r)*(r-l+1)/2;
	}
	printf("%lld\n",ans);
	return 0;
}

3.例题3

求下面式子的值

\sum_{i=1}^{n}\ d(i)

其中，函数d(x)表示正整数x因子个数。

原题在哪里呀？原题在这里

这里我对原题题面进行了化简，原题中的函数f与本题的函数d的功能是一样的。为什么呢，这里简单证明一下：

我们发现，对于正整数

x

的任意因数，一定由

x

的质因数组成。发现这个性质后，我们把就可以把因子个数计数问题转化为一个排列组合问题：在所有

x

的质因数中选择出一个由质因数组成的不同可重集合（也可以为空集）的方案数，集合中的元素元素相乘就是组成的因数。根据~~我们小学二年级学过的~~排列组合知识，我们发现，每一个

x

的质因数

p_i

，有两种选择，即选和不选，选有

c_i

（

p_i

的指数）种方案，根据加法原理，总共有

c_i+1

中方案，再根据乘法原理，总方案数为

\prod_{i=1}^{k} (c_i+1)

与下文中的

n

区分开，上式中的

k

即为原题中的

n

,即质因子种类数。

回归正题，我们发现函数

d(i)

可以写成如下形式

d(i)=\sum_{d \mid i}^{}\ 1

那么代入原式可得

\sum_{i=1}^{n}\ d(i) = \sum_{i=1}^{n}\ \sum_{d \mid i}^{}\ 1

然后我们交换一下求和顺序，将固定i,找

d \mid i

改为固定d,找

d \mid i

且

i \le n

，即

\sum_{d=1}^{n}\ \sum_{d \mid i,i \le n}^{}\ 1

我们发现，第2个求和的意思是所有小于等于n的d的所有的倍数的个数，也就是 $\lfloor\frac{n}{d} \rfloor$ 。
代入原式，即

\sum_{d=1}^{n}\ \lfloor \frac{n}{d} \rfloor

再令

d=i

，可得到

\sum_{i=1}^{n}\ \lfloor \frac{n}{i} \rfloor

我们欣喜地发现，这就是我们的基本问题ya.

我们进行了以上推导，这道题已经完成了大部分，不过若要通过此题，还有一些小细节要注意，我会在代码的注释部分写出。

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll l,r;
ll sum1,sum2;
ll getsum(ll x)
{
	ll ans=0;
	for (ll i=1,j;i<=x;i=j+1)
	{
		j=x/(x/i);
		ans=(ans+((x/i)%mod*(j-i+1)%mod)%mod)%mod;
	}
	return ans%mod;
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>l>>r;
	sum1=getsum(l-1),sum2=getsum(r);//细节1：前缀思想
	//cout<<sum1<<"\n";
	//cout<<sum2<<"\n";
	cout<<((sum2-sum1)%mod+mod)%mod;//细节2：取余。
    //这个我看了讨论区的提示，我把链接放在下面↓
	return 0;
}

感谢大佬の友情提示

这道题虽然结束了，~~但我还想说点废话~~。
其实我一开始并不是这么想的。
当我看到d(x)时，我想到

d(x)=x-\varPhi(x)

其中，

\varPhi(x)

表示x的欧拉函数值。
代入原式可得

\sum_{i=1}^{n}\ d(i) = \sum_{i=1}^{n}\ \big( i-\varPhi(i) \big)

然后我们把求和符号写开

\sum_{i=1}^{n}\ d(i) = \sum_{i=1}^{n}\ i - \sum_{i=1}^{n}\ \varPhi(i)

第一个求和是

O(1)

的，但连续的欧拉函数求和能

O(\sqrt{n})

求解吗？不清楚哎……

感谢大佬KingGojianOfYue为作者指点迷津。

看到这里你应该已经发现了我的错误，第一步就错了。欧拉函数的定义是小于

x

，且与

x

互质的数的个数，则

x-\varPhi(x)

表示小于

x

，且不与

x

互质的数的个数，显然不等于

x

的因数个数。

4.例题4

求下面式子的值

\sum_{i=1}^{n}\ \sigma(i)

其中

\sigma(x)

表示x的因子和。
呵，原题？

有了上一道题的启发，这一道题的思路也很容易得出。
第一步和上题一样：

\sigma(x) = \sum_{d \mid x}^{}\ d

然后再代入原式，可得：

\sum_{i=1}^{n}\ \sum_{d \mid i}^{}\ d

和上题一样，交换求和顺序，得出下面的式子：~~上面详细讲了，这里简单写了~~

\sum_{i=1}^{n}\ i*\lfloor \frac{n}{i} \rfloor

然后我们惊喜的发现，这就是例题1的那个式子，然后我们就可以愉快的写代码了。

愉快の代码时刻↓
和上一道例题的原题一样，这道题也需要前缀思想，只是不用取余了。~~也许双倍经验？~~

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x,y;
ll getsum(ll n)
{
	ll ans=0;
	for (ll i=1,j;i<=n;i=j+1)
	{
		int q=n/i;
		j=n/q;
		ans+=q*(i+j)*(j-i+1)/2;		
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>x>>y;
	cout<<getsum(y)-getsum(x-1);
    return 0;
}

5.例题5

经常莫比乌斯反演的朋友都知道，在莫比乌斯反演中，经常需要计算形如下面的式子

\sum_{i=1}^{min(n,m)}\ \mu(i) \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor

其中

\mu(x)

表示x的莫比乌斯函数的函数值。这道题我没有找到纯原题，但是在莫反中很常用。

对于0基础的小盆友，我贴心的把关于莫比乌斯函数的 前置知识 放在下面，大佬可自动跳过。为了大佬跳过，于是有了标题。

1.莫比乌斯函数定义

莫比乌斯函数的定义如下↓

\mu(x) = \begin{cases} 1 & x=1 \\ (-1)^k & x 是 k 个不同质数的乘积\\ 0 & x含有平方因子（即某个质因数的幂\ge2 \end{cases}

(以上公式摘自deepseek)

没看懂的话我来详细说说后两个：
把x写成算数基本定理的形式

x=p_1^{c_1}p_2^{c_2}……p_n^{c_n}

如果所有c都是1，那么是情况2；
如果存在c不是1，那么是情况3。

2.莫比乌斯函数性质

没什么好说的，直接给式子

\sum_{d \mid n}\mu(d) = \begin{cases} 1 & n=1 \\ 0 & n>1 \\ \end{cases}

3.对原式分块

通过我们的细心观察，我们发现 $\exist$ 一段区间 $[a,b]$ ，使得 $\lfloor \frac{n}{i}\rfloor$ 和 $\lfloor \frac{m}{i}\rfloor$ 的值保持不变。

然后我们讲讲算法步骤：

对于块的左端点i，计算 $q_n= \lfloor \frac{n}{i} \rfloor$ $q_m= \lfloor \frac{m}{i} \rfloor$ 。
算出块的右端点j。 $j = min(\lfloor \frac{n}{q_n} \rfloor,\lfloor \frac{m}{q_m} \rfloor)$ 。
求出每一个块的和。也就是 $\sum_{x=i}^{j}\ \mu(x)\lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor=\sum_{x=i}^{j}\ \mu(x)q_n q_m$ 。
然后将和加到结果里。

下面又是喜闻乐见的代码环节呢~
由于这篇文章主要介绍整除分块，对于线性筛求出莫比乌斯函数值的前缀和代码中省略不写。

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+6;
int s[maxn];//莫比乌斯函数的前缀和
ll n,m;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	ll ans=0;
	ll q=min(n,m);
	for (ll i=1,j;i<=q;i=j+1)
	{
		ll qn=n/i;
		ll qm=m/i;
		j=min(min(n/qn,m/qm),q);
		ans+=(s[i]-s[j-1])*qn*qm;
	}
	cout<<ans;
	return 0;
}

4.写在最后……

AI会帮你的——hsy

有一些确实是借助AI写的，不过~~观众又发现不了~~
本文主要是整除分块的基础内容，整除分块还有很多有趣的内容，我也许还会继续更新。

最后郑重声明：尽管很简单，但作者假期前赶稿，难免会有错误，有大佬发现了请在评论区指出，我会献上最高礼节的。

第一次写文章，管理大大辛苦了，求通过。

最后的最后还有更新日志

快下课了，我明天接着更……// update on 7.9 离暑假还有3天。完成了文章的主体内容并写了第一道例题。

写了一会，我要去做题// update on 7.10 离暑假还有2天。做题任务还没完成，写了第第二道例题。

写了一下午，快吃饭了。// update on 7.11 距离暑假的时间已经可以用小时计算了，距离暑假还有21小时。爆肝了两道的例题，并修改了前面的部分内容。

刷了一晚上水贴，又聊了一会儿天 // 还是7.11 不过距离放假还有18小时，今天周杰伦是不是开演唱会？算了不能再玩了，我要去做题了，可是我要放假。写完了最后一道例题和结尾。

我要放假 // update on 7.12 离放假还有最后1小时。最后审查一遍，并增加部分细节。

// 2025.11.27 时间过得好快呀，更正了部分已知错误，解决了原来没有解决的问题，求管理大大快速通过。

整除分块学习笔记

文章操作

0.前言

1.整除分块の基本问题

2.基本思想&基本定理

3.常见题型

1.例题1

2.例题2

3.例题3

4.例题4

5.例题5

1.莫比乌斯函数定义

2.莫比乌斯函数性质

3.对原式分块

4.写在最后……

最后的最后还有更新日志

相关推荐

评论

整除分块学习笔记