目录

• 数论分块
• 证明法1
• 证明法2
• 复杂度分析
• 例1 [AHOI2005]约数研究
• 例二 [CQOI2007]余数求和
• 例三 约数和
• 写在最后

推一下自己的莫比乌斯反演：

---

数论分块

对于一类含有\(\left\lfloor\frac{n}{i}\right\rfloor\)的求和式 (\(n\) 为常数)，由于\(\left\lfloor\frac{n}{i}\right\rfloor\)单调不增，故存在多个区间\([l,r]\), 使得\(\left\lfloor\frac{n}{i}\right\rfloor = \left\lfloor\frac{n}{j}\right\rfloor(i,j\in [l,r])\) 成立。

对于任意一个\(i\)，最大的满足上式的 \(j=\left\lfloor{\dfrac{n}{\left\lfloor{\dfrac{n}{i}}\right\rfloor}}\right\rfloor\)

证明法1

对于满足\(\left\lfloor\frac{n}{i}\right\rfloor = \left\lfloor\frac{n}{j}\right\rfloor\)的 \(j(i，有：

\[\begin{cases} \left\lfloor{\dfrac{n}{i}}\right\rfloor\le \dfrac{n}{j} = \left\lfloor\dfrac{n}{j}\right\rfloor + r (0\le r < 1)\\ \dfrac{n}{j+1}< \left\lfloor{\dfrac{n}{i}}\right\rfloor \end{cases}\]

则有：

\[\left(\left\lfloor{\dfrac{n}{i}}\right\rfloor\le \dfrac{n}{j}\right)\Longrightarrow \left(\dfrac{n}{\dfrac{n}{j}}\le \dfrac{n}{\left\lfloor{\dfrac{n}{i}}\right\rfloor}\right) \Longrightarrow \left(j \le \dfrac{n}{\left\lfloor\dfrac{n}{i}\right\rfloor}\right)\]

\[\left(\dfrac{n}{j+1}< \left\lfloor{\dfrac{n}{i}}\right\rfloor\right) \Longrightarrow \left(\dfrac{n}{\left\lfloor{\dfrac{n}{i}}\right\rfloor} < \dfrac{n}{\dfrac{n}{j+1}}\right) \Longrightarrow \left(\dfrac{n}{\left\lfloor{\dfrac{n}{i}}\right\rfloor} < j + 1\right)\]

即有：

\[j \le \dfrac{n}{\left\lfloor\dfrac{n}{i}\right\rfloor} < j+1 \]

又 \(j \in \mathbb{N}\)，则 \(j\)最大值为\(\left\lfloor{\dfrac{n}{\left\lfloor\frac{n}{i}\right\rfloor}}\right\rfloor\)

证明法2

\[\begin{aligned} &\left\lfloor\dfrac{n}{i}\right\rfloor \le \dfrac{n}{i}\\ \Longrightarrow &\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{i}\right\rfloor}\right\rfloor \ge \left\lfloor\dfrac{n}{\dfrac{n}{i}}\right\rfloor = \lfloor i\rfloor =i\\ \Longrightarrow &i \le \left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{i}\right\rfloor}\right\rfloor \end{aligned}\]

即 \(j = \left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{i}\right\rfloor}\right\rfloor\)

复杂度分析

引理

\[\forall n\in N,\left| \left\{ \left\lfloor\dfrac{n}{d}\right\rfloor \mid d\in N\right\} \right| \le \left\lfloor{2\sqrt{n}}\right\rfloor \]

\(|V|\)表示集合\(V\)的元素个数

证明

当\(d\le \left\lfloor\sqrt{n}\right\rfloor\)，\(\left\lfloor\dfrac{n}{d}\right\rfloor\)最多有\(\left\lfloor\sqrt{n}\right\rfloor\)种取值。
当\(d\ge \left\lfloor\sqrt{n}\right\rfloor\)，有\(\left\lfloor\dfrac{n}{d}\right\rfloor \le \left\lfloor\sqrt{n}\right\rfloor\)，\(\left\lfloor\dfrac{n}{d}\right\rfloor\)最多有\(\left\lfloor\sqrt{n}\right\rfloor\)种取值。
\(\left\lfloor\dfrac{n}{d}\right\rfloor\)两两不同时集合大小取最大值。
复杂度 \(O(\sqrt n)\)。

---

例1 [AHOI2005]约数研究

令 \(f(i)\) 为 \(i\) 的约数个数，求

\[\sum\limits_{i=1}^{n} f(i) \]

\(n \le 10^6\)

对于 \(i\), 在\(1\sim n\) 中其倍数个数为\(\left\lfloor\dfrac{n}{i}\right\rfloor\)，
则\(1\sim n\)中共有\(\left\lfloor\dfrac{n}{i}\right\rfloor\) 个以其为约数的数。

则\(\sum\limits_{i=1}^{n} f(i) = \sum\limits_{i=1}^{n} \left\lfloor\dfrac{n}{i}\right\rfloor\)

此时直接\(O(n)\)暴力即可通过本题。

---

若 \(n\le 10^{14}\)，考虑数论分块：
由上可知，对于每一个\(l\in [1,n]\), 存在区间\([l, r], r = \left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{l}\right\rfloor}\right\rfloor\),
使得\(\left\lfloor\dfrac{n}{i}\right\rfloor = \left\lfloor\dfrac{n}{j}\right\rfloor(i,j\in [l,r])\)，
区间\([l,r]\) 贡献即为\((r-l+1)\times \left\lfloor\dfrac{n}{l}\right\rfloor\)。

枚举这样的\(j\)计算贡献即可，复杂度\(O(2\sqrt{n})\)

//By:Luckyblock
#include 
#include 
#define ll long long
//=============================================================
int N, ans;
//=============================================================
inline int read()
{
    int f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
//=============================================================
int main()
{
    N = read();
    for(int i = 1, j; i <= N; i = j + 1)
    {
      j = N / (N / i);
      ans += (j - i + 1) * (N / i);
    }
    printf("%d\n", ans);
    return 0;
}

---

例二 [CQOI2007]余数求和

给定\(n, k\)，求

\[\sum\limits_{i=1}^{n} {k\!\!\!\mod\! i} \]

\(n,k \le 10^9\)

进行简单的转化:

\[\begin{aligned} &\sum\limits_{i=1}^{n} {k\!\!\!\mod\! i} \\ = &\sum\limits_{i=1}^{n} k-\left\lfloor\dfrac{k}{i}\right\rfloor \times i\\ = &n \times k - \sum_{i=1}^{n} \left\lfloor\dfrac{k}{i}\right\rfloor \times i \end{aligned}\]

同例一，存在多段\(\left\lfloor\dfrac{k}{i}\right\rfloor\)相等的区间\([l,r]\)，其贡献为 \(-\left\lfloor\dfrac{k}{i}\right\rfloor \times \sum\limits_{i=l}^{r} i\)。
通过数论分块 \(+\) 等差数列求和 得到答案，复杂度\(O(2\sqrt{n})\)。

//By:Luckyblock
#include 
#include 
#define ll long long
//=============================================================
ll N, K, Ans;
//=============================================================
inline ll read()
{
    ll f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
ll GetSum(ll L, ll R) {return (R - L + 1ll) * (L + R) / 2ll;} //等差数列求和
//=============================================================
int main()
{
    N = read(), K = read(), Ans = N * K;
    for(ll i = 1, j; i <= N; i = j + 1ll)
    {
      if(K / i == 0) break; //当k/i = 0时，对答案无贡献
      j = K / (K / i); j = j > N ? N : j;
      Ans -= (K / i) * GetSum(i, j);
    }
    printf("%lld", Ans);
    return 0;
}

---

例三 约数和

定义\(f(n) = \sum\limits_{i\mid n} i\)，给定\(x, y\)，求

\[\sum\limits_{i=x}^{y}f(i) \]

\(x,y \le 2\times 10^9\)

将答案变为前缀和形式:

\(\sum\limits_{i=x}^{y}f(i) = \sum\limits_{i=1}^{y}f(i) - \sum\limits_{i=1}^{x - 1}f(i)\)

简单转化 \(\sum\limits_{i=1}^{n} f(i) = \sum\limits_{i=1}^{n} \sum\limits_{k\mid i} k\)

变换求和顺序，上式即为 \(\sum\limits_{k=1}^{n} \sum\limits_{k\mid i} k (i\le n)\)

\(\sum\limits_{k\mid i}k\) 等价于枚举 \(1\sim n\) 中约数为 \(k\) 的数，
由例一，上式即为 \(\sum\limits_{k=1}^{n} k\times \left\lfloor\dfrac{n}{k}\right\rfloor\)
同例二，通过数论分块 \(+\) 等差数列求和 得到答案，复杂度\(O(2\sqrt{n})\)。

//By:Luckyblock
#include 
#include 
#include 
#define ll long long
//=============================================================
ll x, y;
//=============================================================
inline ll read()
{
    ll f = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
    return f * w;
}
ll GetSum(ll L, ll R) {return (L + R) * (R - L + 1) / 2;}
ll GetAns(ll N)
{
    ll ret = 0;
    for(ll l = 1, r; l <= N; l = r + 1)
    {
      r = N / (N / l);
      ret += GetSum(l, r) * (N / l);
    }
    return ret;
}
//=============================================================
int main()
{
    x = read(), y = read();
    printf("%lld", GetAns(y) - GetAns(x - 1));
    return 0;
}

---

写在最后

数论分块属于小工具一类的知识点。
推式子时要尽量将式子转化为类似形式上。

证明法1是自己yy的，有不当之处请不吝赐教。

参考资料:

莫比乌斯反演 - OI Wiki

无主之地3真好玩，快去买。