整除分块学习笔记

· · 算法·理论

0.前言

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

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

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

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

    1.整除分块の基本问题

求下面式子的值

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

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

这里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$的值，然后乘以区间长度。** 下面我们来讲讲这个算法的步骤 1. 初始化i=1，结果ans=0； 2. 对于每个i，计算$k = \lfloor \frac{n}{i} \rfloor$； 3. 找到最大的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$ 。**~~然而作者并不会证明~~； 4. 将 $k\ast(j-i+1)$ 加到结果中; 5. 令 $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}}

我贴心地帮你把块分号了
通过以上样例我们可以看出，每一个块中都是一个等差数列。 令q = \lfloor \frac{n}{i} \rfloor，即基本问题中每一个块中相等的值，其中：

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

#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。（可以手动验证一下）
所以呢，代码要进行一些小小的改动。

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

#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.

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

#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的那个式子，然后我们就可以愉快的写代码了。

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

#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的值保持不变。

然后我们讲讲算法步骤：

  1. 对于块的左端点i，计算 q_n= \lfloor \frac{n}{i} \rfloor q_m= \lfloor \frac{m}{i} \rfloor 。
  2. 算出块的右端点j。 j = min(\lfloor \frac{n}{q_n} \rfloor,\lfloor \frac{m}{q_m} \rfloor)。
  3. 求出每一个块的和。也就是 \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。
  4. 然后将和加到结果里。

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

#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 时间过得好快呀，更正了部分已知错误，解决了原来没有解决的问题，求管理大大快速通过。