P2261 学习笔记 整除分块详解

整除分块是什么

整除分块（又称数论分块）是数论中一种用于高效计算含有求和公式的技巧。当我们需要计算含有 \(\left \lfloor \dfrac ni \right \rfloor\) 的求和公式的技巧。

当我们需要计算

\[\sum_{i=1}^n f(i) \cdot g(\left \lfloor \frac ni \right \rfloor) \]

时，直接计算的复杂度为 \(O(n)\)，但是若使用整除分块进行解题，利用 \(\left \lfloor \dfrac ni \right \rfloor\) 只有 \(O(\sqrt n)\) 种的性质，可以将时间复杂度降至 \(O(\sqrt n)\)。

整除分块（又称数论分块）是数论中一种用于高效计算含有 \(\left\lfloor \frac{n}{i} \right\rfloor\) 求和公式的技巧。当我们需要计算 \(\sum_{i=1}^{n} f(i) \cdot g\left(\left\lfloor \frac{n}{i} \right\rfloor\right)\) 时，直接计算的时间复杂度为 \(O(n)\)。但利用 \(\left\lfloor \frac{n}{i} \right\rfloor\) 的值只有 \(O(\sqrt{n})\) 种这一性质，可以将计算复杂度降至 \(O(\sqrt{n})\)。

---

整除分块核心思想

单调性与分段常数

对于给定的 \(n\)，考虑函数 \(f(i) = \left\lfloor \frac{n}{i} \right\rfloor\)：

• 当 \(i\) 增大时，\(\left\lfloor \frac{n}{i} \right\rfloor\) 单调不增。

• 存在许多连续的 \(i\) 使得 \(\left\lfloor \frac{n}{i} \right\rfloor\) 的值相同。

• 这些相同值的区间就是“块”。

块的范围

对于给定的一个整数 \(k = \left\lfloor \frac{n}{i} \right\rfloor\)，满足该值的 \(i\) 的最大值是多少？
我们需要找到最大的 \(j\) 使得 \(\left\lfloor \frac{n}{j} \right\rfloor = \left\lfloor \frac{n}{i} \right\rfloor\)。

由定义：

\[\left\lfloor \frac{n}{i} \right\rfloor = k \quad \Rightarrow \quad k \le \frac{n}{i} < k+1 \]

即：

\[\frac{n}{k+1} < i \le \frac{n}{k} \]

但这个推导方向可能有点绕。常用的结论是：

已知当前左端点为 \(l\)，令 \(k = \left\lfloor \frac{n}{l} \right\rfloor\)，则右端点 \(r\) 为：

\[r = \left\lfloor \frac{n}{k} \right\rfloor \]

更简单地：

\[r = \left\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \right\rfloor \]

并且可以保证，对于所有 \(i \in [l, r]\)，\(\left\lfloor \frac{n}{i} \right\rfloor = k\)。

证明思路：

• 对于 \(i \le r\)，有 \(\lfloor n/i \rfloor \ge \lfloor n/r \rfloor = k\)。

• 对于 \(i \ge l\)，有 \(\lfloor n/i \rfloor \le \lfloor n/l \rfloor = k\)。

• 结合两者得 \(\lfloor n/i \rfloor = k\)。

算法流程

要计算 \(\sum_{i=1}^{n} f(i) \cdot g\left(\left\lfloor \frac{n}{i} \right\rfloor\right)\)：

1. 初始化 \(l = 1\)。

2. 当 \(l \le n\) 时：

• 计算 \(k = \lfloor n/l \rfloor\)。

• 计算 \(r = \lfloor n/k \rfloor\)。（注意：当 \(k=0\) 时，需要特殊处理，但通常当 \(l > n\) 时循环结束，实际上在整除分块中 \(k\) 始终 \(\ge 1\)）

• 此时 \([l, r]\) 区间内的 \(\lfloor n/i \rfloor\) 都等于 \(k\)。

• 将这一整块的贡献加到答案中：贡献 = \(g(k) \cdot \sum_{i=l}^{r} f(i)\)。通常如果 \(f(i)\) 是某个简单函数（比如常数 1，或者 \(i\) 本身），我们可以用前缀和快速计算这一段的和。

• 更新 \(l = r + 1\)，继续下一块。

P2261

我们要求：

\[G(n,k)=\sum_{i=1}^n k \bmod i \]

而

\[k \bmod i=k-i \cdot \left \lfloor \frac ki \right \rfloor \]

则

\[G(n,k)=nk-\sum_{i=1}^n i \cdot \left \lfloor \frac ki \right \rfloor \]

令

\[S(n,k)=\sum_{i=1}^n i \cdot \left \lfloor \frac ki \right \rfloor \]

所求的

\[G(n,k)=nk-S(n,k) \]

问题就转化为求 \(S(n,k)\)。

• 若 \(i \ge k\)，整除分块即可。
• 若 \(i < k\)，对 \(S(n,k)\) 的贡献为 \(0\)，不进行计算。

故

\[S(n,k)=\sum_{i=1}^{\min(n,k)} i \cdot \left \lfloor \frac ki \right \rfloor \]

进行整除分块即可。

code

#include <bits/stdc++.h>
#define pub public:
#define pri private:
#define fri friend:
#define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", stdout)
#define Cfile(s) fclose(stdin), fclose(stdout)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;using ll = long long;
using ull = unsigned long long;
using lb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;constexpr int mod = 998244353;
constexpr int maxn = 2e5 + 5;ll n, k;ll calcS(ll n, ll k){ll l = 1, j = 0, r = 0, num = 0;while (l <= min(n, k)){num = k / l;r = min(k / num, min(n, k));j += num * (l + r) * (r - l + 1) / 2;l = r + 1;}return j;
}ll calcG(ll n, ll k){return n * k - calcS(n, k);
}int main() {freopen("std.in", "r", stdin);freopen("std.out", "w", stdout);fast;cin >> n >> k;cout << calcG(n, k) << endl;return 0;
}