數論分塊

數論分塊可以快速計算一些含有除法向下取整的和式（即形如 $\sum_{i=1}^nf(i)g(\left\lfloor\dfrac ni\right\rfloor)$ 的和式）。當可以在 $O(1)$ 內計算 $f(r)-f(l)$ 或已經預處理出 $f$ 的前綴和時，數論分塊就可以在 $O(\sqrt n)$ 的時間內計算上述和式的值。

它主要利用了富比尼定理（Fubini's theorem），將 $\left\lfloor\dfrac ni\right\rfloor$ 相同的數打包同時計算。

富比尼定理

又稱「算兩次」，以意大利數學家圭多·富比尼（Guido Fubini）命名。富比尼定理的積分形式：只要二重積分 $\int\int |f(x,y)|dxdy$ 有界，則可以逐次計算二重積分，並且可以交換逐次積分的順序。積分號也是特殊的求和號，因此在一般求和中，富比尼定理往往呈現為更換計數順序，即交換兩個求和號。組合數學中的富比尼定理表現為，用兩種不同的方法計算同一個量，從而建立相等關係。

例如這裏的雙曲線下整點的圖片：

雙曲線下整點

圖中共分為了 $5$ 塊，這 $5$ 塊整點的最大縱座標都相同。如果統計整點的個數，可以從縱向計數改為橫向計數，直接計算 $5$ 個矩形即可。

引理 1

\[ \forall a,b,c\in\mathbb{Z},\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor \]

略證：

\[ \begin{aligned} &\frac{a}{b}=\left\lfloor\frac{a}{b}\right\rfloor+r(0\leq r<1)\\ \implies &\left\lfloor\frac{a}{bc}\right\rfloor =\left\lfloor\frac{a}{b}\cdot\frac{1}{c}\right\rfloor =\left\lfloor \frac{1}{c}\left(\left\lfloor\frac{a}{b}\right\rfloor+r\right)\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c} +\frac{r}{c}\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor\\ &&\square \end{aligned} \]

關於證明最後的小方塊

QED 是拉丁詞組「Quod Erat Demonstrandum」（這就是所要證明的）的縮寫，代表證明完畢。現在的 QED 符號通常是 $\blacksquare$ 或者 $\square$。（維基百科）

引理 2

\[ \forall n \in \mathbb{N}_{+}, \left|\left\{ \lfloor \frac{n}{d} \rfloor \mid d \in \mathbb{N}_{+},d\leq n \right\}\right| \leq \lfloor 2\sqrt{n} \rfloor \]

$|V|$ 表示集合 $V$ 的元素個數

略證：

對於 $d\leq \left\lfloor\sqrt{n}\right\rfloor$，$\left\lfloor\frac{n}{d}\right\rfloor$ 有 $\left\lfloor\sqrt{n}\right\rfloor$ 種取值

對於 $d> \left\lfloor\sqrt{n}\right\rfloor$，有 $\left\lfloor\frac{n}{d}\right\rfloor\leq\left\lfloor\sqrt{n}\right\rfloor$，也只有 $\left\lfloor\sqrt{n}\right\rfloor$ 種取值

綜上，得證

數論分塊結論

對於常數 $n$，使得式子

\[ \left\lfloor\dfrac ni\right\rfloor=\left\lfloor\dfrac nj\right\rfloor \]

成立的最大的滿足 $i\leq j\leq n$ 的 $j$ 的值為 $\left\lfloor\dfrac n{\lfloor\frac ni\rfloor}\right\rfloor$。即值 $\left\lfloor\dfrac ni\right\rfloor$ 所在的塊的右端點為 $\left\lfloor\dfrac n{\lfloor\frac ni\rfloor}\right\rfloor$。

證明

令 $k=\left\lfloor\dfrac ni\right\rfloor$，可以知道 $k\leq\dfrac ni$。

\[ \begin{aligned} &\therefore \left\lfloor\dfrac nk\right\rfloor\geq\left\lfloor\dfrac n{\frac ni}\right\rfloor=\lfloor i\rfloor=i\\ &\therefore j=\max{\text{滿足條件的所有 }i}=i_{\max}=\left\lfloor\dfrac nk\right\rfloor=\left\lfloor\dfrac n{\left\lfloor\dfrac ni\right\rfloor}\right\rfloor \square \end{aligned} \]

過程

數論分塊的過程大概如下：考慮和式

$\sum_{i=1}^nf(i)\left\lfloor\dfrac ni\right\rfloor$

那麼由於我們可以知道 $\left\lfloor\dfrac ni\right\rfloor$ 的值成一個塊狀分佈（就是同樣的值都聚集在連續的塊中），那麼就可以用數論分塊加速計算，降低時間複雜度。

利用上述結論，我們先求出 $f(i)$ 的 前綴和（記作 $s(i)=\sum_{j=1}^i f(j)$），然後每次以 $[l,r]=[l,\left\lfloor\dfrac n{\lfloor\frac ni\rfloor}\right\rfloor]$ 為一塊，分塊求出貢獻累加到結果中即可。

偽代碼如下：

\[ \begin{array}{ll} 1 & \text{獲取 $f(i)$ 函數的前綴和，記為 $s(i)$.} \\ 2 & l \gets 1\\ 3 & r \gets 0\\ 4 & \textit{result} \gets 0 \\ 5 & \textbf{while } l \leq n \textbf{ do} : \\ 6 & \qquad r \gets \left\lfloor \dfrac{n}{\lfloor n/l \rfloor} \right\rfloor\\ 7 & \qquad \textit{result} \gets \textit{result} + [s(r)-s(l-1)] \times\left\lfloor \dfrac{n}{l} \right\rfloor\\ 8 & \qquad l \gets r+1\\ 9 & \textbf{end while }\\ \end{array} \]

最終得到的 $result$ 即為所求的和式。

例題：UVa11526 H(n)

題意：$T$ 組數據，每組一個整數 $n$。對於每組數據，輸出 $\sum_{i=1}^n\left\lfloor\dfrac ni\right\rfloor$。

思路：如上推導，對於每一塊相同的 $\left\lfloor\dfrac ni\right\rfloor$ 一起計算。時間複雜度為 $O(T\sqrt n)$。

參考實現

long long H(int n) {
  long long res = 0;  // 儲存結果
  int l = 1, r;       // 塊左端點與右端點
  while (l <= n) {
    r = n / (n / l);  // 計算當前塊的右端點
    res += (r - l + 1) * 1LL *
           (n / l);  // 累加這一塊的貢獻到結果中。乘上 1LL 防止溢出
    l = r + 1;  // 左端點移到下一塊
  }
  return res;
}

N 維數論分塊

求含有 $\left\lfloor\dfrac {a_1}i\right\rfloor$、$\left\lfloor\dfrac {a_2}i\right\rfloor\cdots\left\lfloor\dfrac {a_n}i\right\rfloor$ 的和式時，數論分塊右端點的表達式從一維的 $\left\lfloor\dfrac ni\right\rfloor$ 變為 $\min\limits_{j=1}^n\{\left\lfloor\dfrac {a_j}i\right\rfloor\}$，即對於每一個塊的右端點取最小（最接近左端點）的那個作為整體的右端點。可以藉助下圖理解：

多維數論分塊圖解

一般我們用的較多的是二維形式，此時可將代碼中 r = n / (n / i) 替換成 r = min(n / (n / i), m / (m / i))。

習題

CQOI2007 餘數求和（需要一點轉化和特判）
UVa11526 H(n)（幾乎可以當做模板題）
POI2007 ZAP-Queries（數論分塊一般配合莫比烏斯反演用以進一步降低複雜度；本題需要用到 $[n=1]=\sum_{d|n}\mu(n)$ 這一條莫反結論）

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用