数论求和题型整理

数论求和题表面上可能在统计互质数对、固定 GCD、GCD 的函数、LCM、约数个数和等完全不同的对象，但很多题最后都会经历相似的过程：先按 GCD 或整除关系重新分类，再利用 Möbius 反演或狄利克雷卷积把条件拆开，最后通过整除分块与算术函数前缀和完成求和。

这类题真正需要整理的不是每一道题最后得到的公式，而是这些公式为什么总会经过“展开 → 交换求和顺序 → 代换 / 合并指标 → 分离变量 → 处理算术函数前缀和”这一套相似的过程。

由于本页面长度限制，具体的代码实现详见 数论求和题型整理_代码 一文。

零、预备理论

1. 狄利克雷卷积

对于两个算术函数 $f,g$，定义狄利克雷卷积：

$$(f*g)(n) = \sum_{d\mid n} f(d)g\left(\frac nd\right)$$

其中常见的函数有：

• 常数函数 $1(n) = 1$ | 单位元 $\varepsilon(n) = [n == 1]$；
• 恒等函数 $\operatorname{id}(n)=n$ | $\operatorname{id}_k(n)=n^k$；
• 莫比乌斯函数 $\mu$ | 欧拉函数 $\varphi$。

卷积满足交换律和结合律，并且 $1*\mu=\varepsilon$，因此 $\mu$ 可以看成常数函数 $1$ 在狄利克雷卷积下的逆元。

2. 莫比乌斯反演

若 $\displaystyle F(n) = \sum_{d \mid n}f(d)$，也就是 $F = f * 1$，那么两边卷积 $\mu$ 得 $f = F * \mu$。

于是就有 $\displaystyle f(n) = \sum_{d \mid n} \mu(d) F\left(\frac{n}{d}\right)$。在 GCD 计数中最常用的是把 $[x=1]$ 展开。

由 $\displaystyle \sum_{d\mid x}\mu(d)=[x=1]$，令 $x=\gcd(i,j)$，可以得到：

【M1】互质条件展开

$\displaystyle [\gcd(i,j) = 1] = \sum_{d \mid \gcd(i, j)} \mu(d) = \sum_{d \mid i, d \mid j} \mu(d)$

后续遇到互质条件时，可以直接使用【M1】展开。

3. 欧拉函数恒等式

经典恒等式 $\displaystyle \sum_{d\mid n}\varphi(d)=n$，也就是 $\varphi * 1 = id$。

因此可以把一个整数本身拆成其约数上的 $\varphi$ 贡献。令 $n=\gcd(i,j)$，得到：

【E1】GCD 的欧拉展开

$\displaystyle \gcd(i, j) = \sum_{d \mid \gcd(i, j)} \varphi(d)$

后续遇到 GCD 本身作为权值时，可以优先使用【E1】。

4. 一般 $F(\gcd)$ 展开

若被加数不是 $\gcd(i,j)$，而是一般的 $F(\gcd(i,j))$，令 $G = F * \mu$，

由莫比乌斯反演可知 $F=G*1$，所以 $\displaystyle F(\gcd(i,j)) = \sum_{d \mid \gcd(i, j)}G(d)$。交换求和顺序后：

【F1】一般

$F(\gcd)$ 求和

若 $G=F*\mu$，则：

$$\sum_{i=1}^{n}\sum_{j=1}^{m}F(\gcd(i,j)) = \sum_{d=1}^{\min(n,m)} G(d) \left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor$$

P2398 中 $F=\operatorname{id}$，于是 $G=\varphi$；P4449 中 $F=\operatorname{id}_k$，于是 $G=\operatorname{id}_k*\mu$。

几个常见的 $F$ 可以直接代入【F1】理解：

$F$	$G=F*\mu$	对应结果
$1$	$\varepsilon$	$\displaystyle \sum_{i\le n}\sum_{j\le m}1=nm$
$\operatorname{id}$	$\varphi$	GCD 求和
$\operatorname{id}_k$	$J_k$	GCD 的 $k$ 次幂求和
$d=1*1$	$1$	$\displaystyle \sum d(\gcd(i,j))=\sum_{t\le\min(n,m)}\left\lfloor\frac nt\right\rfloor\left\lfloor\frac mt\right\rfloor$
$\varphi$	$\varphi*\mu$	继续按照一般 $F(\gcd)$ 处理

这里的目的不是记住所有结果，而是熟悉一个动作：给定 $F$，先求 $F*\mu$，再直接套【F1】。

5. 整除分块

若最终式中同时出现 $\lfloor n/d\rfloor$ 与 $\lfloor m/d\rfloor$，它们会在一段连续区间中保持不变。

【B1】二维整除分块

当前左端点为 $l$，记 $\displaystyle v_n=\left\lfloor\frac nl\right\rfloor,\ v_m=\left\lfloor\frac ml\right\rfloor$。

那么这一块的右端点为 $\displaystyle r=\min\left(\left\lfloor\frac n{v_n}\right\rfloor,\left\lfloor\frac m{v_m}\right\rfloor\right)$。

如果算术函数 $g$ 的前缀和为 $\displaystyle G(x)=\sum_{i=1}^{x}g(i)$，这一块只需要查询 $G(r)-G(l-1)$。

6. 常见推导动作

后面的题目基本都可以拆成下面几个动作：

1. 展开：使用【M1】、【E1】或【F1】把条件或权值展开成约数和；
2. 交换求和顺序：从枚举 $(i,j)$ 改成先枚举约数或公共尺度；
3. 代换：常见为 $i=dx,j=dy$，拆出公共因子；
4. 合并指标：例如令 $T=pd$、$T=dk$；
5. 分离变量：把二重和拆成两个一元前缀和；
6. 优化前缀和：最后再考虑线性筛、整除分块、杜教筛或离线数据结构。

后面的题目会尽量把“文字推导”和“公式推导”分开。文字部分说明为什么这样变，公式部分只保留真正需要记忆的变形链。

---

一、互质计数与固定 GCD

这一类问题的核心是统计满足 $\gcd(i,j)=k$ 的数对。最基本的变换是先除去固定的 GCD，把问题化成互质计数，再利用【M1】展开互质条件。

1. 互质数对计数

Q1

P2158 [SDOI2008] 仪仗队
在 $N\times N$ 的方阵中统计从左下角能够看到的同学数量，数据范围为 $N\le 40000$。

除去两条坐标轴上的边界后，一个位置可见当且仅当它与起点之间没有其他格点，也就是相对坐标互质。两条坐标轴各贡献一个可见点，内部互质点利用对称性统计，因此 $N>1$ 时答案为 $\displaystyle 2\sum_{i=1}^{N-1}\varphi(i)+1$；特别地，$N=1$ 时答案为 $0$。

推广本题到矩形后：形式化描述为 $\displaystyle Ans=\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=1]$，再使用【M1】展开互质条件。

$$\begin{aligned} Ans &= \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d\mid i,\ d\mid j}\mu(d) \\ &= \sum_{d=1}^{\min(n,m)} \mu(d) \left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor \end{aligned}$$

由此得到 GCD 计数中最基础的变形：用莫比乌斯函数消掉互质条件，剩下的只是“有多少个数能被 $d$ 整除”。

2. 固定 GCD

Q2

P3455 [POI2007] ZAP-Queries
不超过 $5\times10^4$ 组询问给出 $n,m,k$，其中 $n,m\le5\times10^4$，统计满足 $\gcd(i,j)=k$ 的有序数对数量。

如果 $\gcd(i,j)=k$，令 $i=ki',j=kj'$，则 $\gcd(i',j')=1$。

因此原问题直接缩放为 $\lfloor n/k\rfloor\times\lfloor m/k\rfloor$ 中的互质数对计数，随后套用 Q1。

$$Ans = \sum_{d=1}^{\min(n/k,m/k)} \mu(d) \left\lfloor\frac{n}{kd}\right\rfloor \left\lfloor\frac{m}{kd}\right\rfloor$$

固定 GCD 的标准动作就是：先除去已知 GCD，再做互质计数。

3. 任意矩形中的固定 GCD

Q3

P2522 [HAOI2011] Problem b
多组询问给出两个整数区间 $[a,b]$、$[c,d]$ 和整数 $k$，端点不超过 $5\times10^4$，统计满足 $\gcd(x,y)=k$ 的有序数对。

Q2 解决的是前缀矩形 $[1,n]\times[1,m]$。本题只是把范围改成任意矩形，因此再套一层二维容斥即可。

记 $F(n,m,k)$ 为 Q2 的前缀答案，则：

$$Ans = F(b,d,k)-F(a-1,d,k)-F(b,c-1,k)+F(a-1,c-1,k)$$

本题没有新的数论变形，只是在固定 GCD 模型外增加二维前缀容斥。

---

二、GCD 满足某种性质

第一节中 GCD 的值是固定的，本节进一步要求 GCD 属于某个集合。最直接的思路仍然是枚举所有合法的 GCD，再把每一个固定值化成互质计数。

1. 枚举合法 GCD

Q4

P2568 GCD
统计 $1\le x,y\le n$ 中满足 $\gcd(x,y)$ 为质数的有序数对数量，其中 $n\le10^7$。

若 $\gcd(x,y)=p$，其中 $p$ 为质数，令 $x=pa,y=pb$，就有 $\gcd(a,b)=1$。

因此可以枚举所有质数 $p$，对每个 $p$ 统计一个 $\lfloor n/p\rfloor\times\lfloor n/p\rfloor$ 中的互质数对。

记 $C(N)$ 为 $1\le a,b\le N$ 中的互质数对数量，根据 Q1 有：$\displaystyle C(N) = \sum_{d=1}^{N} \mu(d) \left\lfloor \frac{N}{d} \right\rfloor^{2}$。

因此答案为：

$$\begin{aligned} Ans &= \sum_{p} C\left(\left\lfloor\frac np\right\rfloor\right) \\ &= \sum_{p} \sum_{d=1}^{\lfloor n/p\rfloor} \mu(d) \left\lfloor\frac{n}{pd}\right\rfloor^2 \end{aligned}$$

对于正方形范围，还可以利用互质点的对称性得到 $\displaystyle C(N)=2\sum_{i=1}^{N}\varphi(i)-1$。

由此，“GCD 是质数”可以先理解成：枚举所有合法的固定 GCD，再累加这些固定 GCD 的答案。

2. 合并所有合法 GCD 的贡献

Q5

P2257 YY 的 GCD
共 $10^4$ 组询问给出 $n,m\le10^7$，统计满足 $\gcd(x,y)$ 为质数的有序数对。

仍然先枚举最终的质数 GCD $p$。除去 $p$ 后使用【M1】展开互质条件：

$$Ans = \sum_{p}\sum_{d} \mu(d) \left\lfloor\frac{n}{pd}\right\rfloor \left\lfloor\frac{m}{pd}\right\rfloor$$

令 $T=pd$，把所有满足 $pd=T$ 的贡献合并：

$$Ans = \sum_{T=1}^{\min(n,m)} \left\lfloor\frac{n}{T}\right\rfloor \left\lfloor\frac{m}{T}\right\rfloor \sum_{p \mid T} \mu\left(\frac{T}{p}\right)$$

记 $\displaystyle g(T)=\sum_{p\mid T}\mu\left( \frac{T}{p} \right)$，最终就得到：$\displaystyle Ans = \sum_{T=1}^{\min(n,m)} g(T) \left\lfloor\frac{n}{T}\right\rfloor \left\lfloor\frac{m}{T}\right\rfloor$。

相比 Q4，这里不再对每个质数分别完成一次统计，而是把所有合法 GCD 的贡献合并到一个算术函数 $g$ 中。预处理 $g$ 的前缀和后，就可以直接使用【B1】整除分块。

GCD 满足某种性质

GCD 属于某个集合时，可以先枚举所有合法 GCD，再把每个固定值化成互质计数。

如果逐个枚举复杂度过高，就继续交换求和顺序，把所有合法 GCD 的贡献合并到一个算术函数中。

---

三、对 GCD 赋权

前两节统计的都是某个条件是否成立，本节进一步考虑 $\gcd(i,j)$ 本身，或者 $\gcd(i,j)$ 的函数作为权值。

1. 一维 GCD 求和

Q6

P2303 [SDOI2012] Longge 的问题
给定整数 $n$，求 $\displaystyle \sum_{i=1}^{n}\gcd(i,n)$。

被加数就是 GCD 本身，直接使用【E1】展开。交换求和顺序以后，固定 $d\mid n$，只需要统计 $1\sim n$ 中 $d$ 的倍数个数。

$$\begin{aligned} Ans &= \sum_{i=1}^{n}\sum_{d\mid\gcd(i,n)}\varphi(d) \\ &= \sum_{d\mid n}\varphi(d)\sum_{1\le i\le n,\ d\mid i}1 \\ &= \sum_{d\mid n}\varphi(d)\frac nd \end{aligned}$$

从另一个角度，也可以直接按照 $d=\gcd(i,n)$ 分类。

若 $\gcd(i,n)=d$，令 $i=dx$，则 $\gcd\left(x,\frac nd\right)=1$，这一类有 $\varphi(n/d)$ 个，因此同样得到 $\displaystyle Ans=\sum_{d\mid n}d\varphi(n/d)$。

这道题可以看作 $F(\gcd)$ 求和的一维原型。

2. 二维 GCD 求和

Q7

P2398 GCD SUM
给定 $n\le10^5$，求所有 $1\le i,j\le n$ 的 $\gcd(i,j)$ 之和。

这就是 Q6 的二维版本，继续直接使用【E1】展开 GCD。

$$\begin{aligned} Ans &= \sum_{i=1}^{n}\sum_{j=1}^{n} \sum_{d\mid\gcd(i,j)}\varphi(d) \\ &= \sum_{d=1}^{n} \varphi(d) \left\lfloor\frac nd\right\rfloor^2 \end{aligned}$$

若范围为一般的 $n,m$，则：

$$Ans = \sum_{d=1}^{\min(n,m)} \varphi(d) \left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor$$

Q6 到 Q7 的变化只有一层：从固定一侧的一维 GCD 求和，推广到二维矩形上的 GCD 求和。

3. GCD 的幂次求和

Q8

P4449 于神之怒加强版
多组询问给出 $n,m\le5\times10^6$ 和固定指数 $k$，求 $\displaystyle \sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)^k$。

上一题使用的是 $F(x)=x$，对应【E1】。现在换成 $F(x)=x^k$，直接使用【F1】即可。

令 $J_k=\operatorname{id}_k*\mu$，那么 $\displaystyle n^k=\sum_{d\mid n}J_k(d)$，于是：

$$\begin{aligned} Ans &= \sum_{i=1}^{n}\sum_{j=1}^{m} \sum_{d\mid\gcd(i,j)}J_k(d) \\ &= \sum_{d=1}^{\min(n,m)} J_k(d) \left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor \end{aligned}$$

其中 $\displaystyle J_{k}(n) = \sum_{d \mid n} \mu(d) \left( \frac{n}{d} \right)^{k}$，特别地，$J_1=\varphi$。因此 Q7 的欧拉展开正是这一模型在 $k=1$ 时的特殊情况。

从 GCD 到一般

$F(\gcd)$
当被加数就是 $\gcd(i,j)$ 时，直接使用【E1】。

当被加数推广成一般 $F(\gcd(i,j))$ 时，直接使用【F1】，也就是先求 $G=F*\mu$，再处理算术函数 $G$ 的前缀和。

四、带权 GCD 与 LCM 求和

如果原式除了 GCD 以外，还显式含有 $i,j$ 的权值，就需要继续判断这些权值能否在代换后被拆开。

1. LCM 求和

Q9

P1829 [国家集训队] Crash 的数字表格 / JZPTAB
给定 $n,m$，求 $\displaystyle \sum_{i=1}^{n}\sum_{j=1}^{m}\operatorname{lcm}(i,j)$。

由于 $\operatorname{lcm}(i,j)=\frac{i \cdot j}{\gcd(i,j)}$，它并不是一个只依赖 $\gcd(i,j)$ 的函数，因此不能直接使用【F1】。

令 $d=\gcd(i,j)$，再写成 $i=dx,j=dy$，其中 $\gcd(x,y)=1$。此时 $\operatorname{lcm}(i,j)=dxy$，于是先提取真实的 GCD，再使用【M1】展开互质条件。

$$\begin{aligned} Ans &= \sum_{d=1}^{\min(n,m)} d \sum_{x\le n/d}\sum_{y\le m/d} xy[\gcd(x,y)=1] \\ &= \sum_d d\sum_k\mu(k)k^2 S\left(\left\lfloor\frac{n}{dk}\right\rfloor\right) S\left(\left\lfloor\frac{m}{dk}\right\rfloor\right) \end{aligned}$$

其中 $S(x)=\frac{x(x+1)}2$。

令 $T=dk$，合并指标：

$$Ans = \sum_{T=1}^{\min(n,m)} S\left(\left\lfloor\frac nT\right\rfloor\right) S\left(\left\lfloor\frac mT\right\rfloor\right) T\sum_{k\mid T}\mu(k)k$$

记 $\displaystyle h(T)=T\sum_{k\mid T}\mu(k)k$，最终得到：

$$Ans = \sum_{T=1}^{\min(n,m)} h(T) S\left(\left\lfloor\frac nT\right\rfloor\right) S\left(\left\lfloor\frac mT\right\rfloor\right)$$

这里还有一个实现上很有用的性质：$h$ 是积性函数。对于素数幂 $p^a$，只有 $1,p$ 两个约数的 Möbius 值非零，因此：

$$h(p^a)=p^a(1-p)$$

所以除了按约数倍数关系预处理 $h$，也可以利用积性函数的性质在线性筛中直接递推。

这里相比普通互质计数，多出来的是 $xy$ 权值，所以内层从“统计数量”变成了“统计权值和”。

难度跨越好像有点大，尝试着接受它吧。

2. 带 $ij$ 权值的 GCD 求和

Q10

P3768 简单的数学题

给定 $n\le 10^{10}$ 和质数 $p$，求 $\displaystyle \sum_{i=1}^{n}\sum_{j=1}^{n}ij\gcd(i,j)$，并对 $p$ 取模。

虽然外面多了 $ij$ 权值，但 GCD 本身仍然可以直接使用【E1】展开。

先利用 $\displaystyle \gcd(i,j)=\sum_{d\mid\gcd(i,j)}\varphi(d)$，再交换枚举顺序。

此时有 $\displaystyle Ans=\sum_{d=1}^{n}\varphi(d)\sum_{\substack{i\le n\ d\mid i}}\sum_{\substack{j\le n\ d\mid j}}ij$，其中外层枚举的是同时整除 $i,j$ 的约数 $d$。

接下来令 $i=da,\ j=db$，则 $a,b\le\left\lfloor\frac nd\right\rfloor$，同时权值变成 $ij=d^2ab$。

因此有 $\displaystyle Ans=\sum_{d=1}^{n}d^2\varphi(d)\sum_{a\le\lfloor n/d\rfloor}\sum_{b\le\lfloor n/d\rfloor}ab$，而 $a,b$ 的取值相互独立。

记 $\displaystyle S(t)=\sum_{k=1}^{t}k$，则二重求和可以拆成两个整数前缀和，则 $\displaystyle Ans=\sum_{d=1}^{n}d^2\varphi(d)S\left(\left\lfloor\frac nd\right\rfloor\right)^2$。

因此真正需要维护的是算术函数 $h(d)=d^2\varphi(d)$ 的前缀和。

记 $\displaystyle H(n)=\sum_{d=1}^{n}d^2\varphi(d)$，数据范围小时可以筛出 $\varphi$ 后直接预处理；数据范围较大时，再利用杜教筛计算 $H(n)$。

杜教筛处理 $H(n)$

考虑 $h(n)=n^2\varphi(n)$ 与 $\operatorname{id}_2(n)=n^2$ 的狄利克雷卷积：

$$(h*\operatorname{id}_2)(n) = \sum_{d\mid n} d^2\varphi(d) \left(\frac nd\right)^2 = n^2\sum_{d\mid n}\varphi(d) = n^3$$

因此：$h * \operatorname{id}_2 = \operatorname{id}_3$。

记 $\displaystyle H(n)=\sum_{i=1}^{n}h(i)$，对卷积两边做前缀求和：

$$\sum_{x=1}^{n}x^3 = \sum_{d=1}^{n} d^2 H\left(\left\lfloor\frac nd\right\rfloor\right)$$

把 $d=1$ 的项提出：

$$H(n) = \sum_{x=1}^{n}x^3 - \sum_{d=2}^{n} d^2 H\left(\left\lfloor\frac nd\right\rfloor\right)$$

右侧再按照整除商相同的区间分块即可。

3. 一般带权形式

更一般地，如果原式形如 $\displaystyle \sum i^a j^b F(\gcd(i,j))$，可以先令 $d=\gcd(i,j)$，写成 $i=dx,j=dy$。

此时：

$$i^a j^b F(\gcd(i,j)) = d^{a+b}x^a y^b F(d)$$

于是公共尺度 $d$ 与剩余变量 $x,y$ 被拆开，而 $x,y$ 满足 $\gcd(x,y)=1$。之后再根据 $F$ 的形式决定直接做【F1】，还是对互质条件使用【M1】。

因此带权问题的关键是判断：换元以后，额外权值能否被拆成关于 $d$、$x$、$y$ 的乘积。

带额外权值

P1829 不能直接使用【F1】，需要先提取真实的 GCD，再使用【M1】处理互质条件。

P3768 则可以直接使用【E1】，因为外部的 $ij$ 权值在代换以后可以完全分离。

---

五、非 $F(\gcd)$ 型的卷积分离

并不是所有二元函数都能写成 $F(\gcd(i,j))$。如果这一点做不到，就需要寻找新的恒等式，把原本耦合的二元函数拆成两个一元函数。

1. 约数个数和

Q11

P3327 [SDOI2015] 约数个数和
多组询问给出 $n,m$，求 $\displaystyle \sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)$，其中 $d(x)$ 表示 $x$ 的正约数个数。

$d(ij)$ 不能只由 $\gcd(i,j)$ 决定，因此不能直接使用【F1】。

这里需要利用约数恒等式：$\displaystyle d(ij) = \sum_{k\mid\gcd(i,j)} \mu(k) d\left(\frac ik\right) d\left(\frac jk\right)$，这里简要推导这个恒等式是怎么来的。

先从约数的组合方式出发。$ij$ 的每一个约数都可以唯一写成 $xy$，其中 $x\mid i$、$y\mid j$，并要求 $x,y$ 互质，因此：

$$d(ij) = \sum_{x\mid i}\sum_{y\mid j} [\gcd(x,y)=1]$$

对互质条件使用【M1】展开：

$$\begin{aligned} d(ij) &= \sum_{x\mid i}\sum_{y\mid j} \sum_{k\mid\gcd(x,y)}\mu(k) \\ &= \sum_{k\mid\gcd(i,j)} \mu(k) d\left(\frac ik\right) d\left(\frac jk\right) \end{aligned}$$

代入原式并交换求和顺序：

$$\begin{aligned} Ans &= \sum_{i=1}^{n}\sum_{j=1}^{m} \sum_{k\mid\gcd(i,j)} \mu(k) d\left(\frac ik\right) d\left(\frac jk\right) \\ &= \sum_{k=1}^{\min(n,m)} \mu(k) \left( \sum_{x=1}^{\lfloor n/k\rfloor}d(x) \right) \left( \sum_{y=1}^{\lfloor m/k\rfloor}d(y) \right) \end{aligned}$$

记：

$$F(N) = \sum_{i=1}^{N}d(i) = \sum_{t=1}^{N} \left\lfloor\frac Nt\right\rfloor$$

于是：

$$Ans = \sum_{k=1}^{\min(n,m)} \mu(k) F\left(\left\lfloor\frac nk\right\rfloor\right) F\left(\left\lfloor\frac mk\right\rfloor\right)$$

这里莫比乌斯反演的作用重点是把 $d(ij)$ 这个耦合的二元算术函数拆成两个独立的一元前缀函数。

---

六、公式推完以后：前缀和与整除分块

前面的题型负责“怎样推公式”。公式得到以后，实现层面通常只剩下算术函数前缀和与整除分块。

1. 小范围：筛法预处理

P3455、P2522 需要 $\mu$ 的前缀和，P2398 需要 $\varphi$ 的前缀和；P2257、P1829、P4449 则需要先构造对应的算术函数，再维护它们的前缀和。

当数据范围允许预处理到 $\min(n,m)$ 时，直接使用线性筛或约数倍数枚举即可。

2. 整除分块

最终式如果形如：

$$\sum_d g(d) A\left(\left\lfloor\frac nd\right\rfloor\right) B\left(\left\lfloor\frac md\right\rfloor\right)$$

并且已经有 $g$ 的前缀和，那么直接使用【B1】按整除商相同的区间分块即可。

3. 大范围：杜教筛

杜教筛处理的是“最终需要的积性函数前缀和无法直接筛到上界”的情况。

例如 P3768 最终需要 $\displaystyle H(n)=\sum_{i=1}^{n}i^2\varphi(i)$。前面的题型公式没有变化，只是这个前缀和不能直接预处理，因此再利用狄利克雷卷积关系构造递归。

三类工具的职责

莫比乌斯反演与狄利克雷卷积负责推公式；
整除分块负责减少外层不同整除商的枚举次数；
线性筛或杜教筛负责回答最终算术函数的前缀和。

---

七、进阶变化

在经典模型之上，还会继续增加动态限制、阈值限制，甚至把最终聚合方式从加法改成乘法。

1. 带阈值的 $F(\gcd)$ 求和

Q12

P3312 [SDOI2014] 数表
不超过 $2\times10^4$ 组询问给出 $n,m\le10^5$ 和 $|a|\le10^9$，只统计 $\sigma(\gcd(i,j))\le a$ 的位置贡献。

由于约数和恒为正数，当 $a\le0$ 时没有任何位置满足限制，答案直接为 $0$。下面只讨论 $a>0$ 的询问。

定义 $F_a(x)=\sigma(x)[\sigma(x)\le a]$，那么本题仍然是一般的 $F(\gcd)$ 模型，可以直接使用【F1】。

令 $G_{a} = F_{a} * \mu$，则：

$$Ans = \sum_{t=1}^{\min(n,m)} G_a(t) \left\lfloor\frac{n}{t}\right\rfloor \left\lfloor\frac{m}{t}\right\rfloor$$

其中：

$$G_a(t) = \sum_{d\mid t} F_a(d) \mu\left(\frac td\right)$$

真正新增的难点在于 $a$ 会随着询问变化，所以当前有效的 $F_a(d)$ 也在变化。

把所有 $d$ 按照 $\sigma(d)$ 从小到大排序，并把询问按 $a$ 排序。

当某个 $d$ 第一次满足 $\sigma(d)\le a$ 时，它会对所有 $t=dk$ 增加：

$$\Delta G_a(dk) = \sigma(d)\mu(k)$$

因此可以离线逐步激活这些贡献，并使用树状数组维护当前算术函数 $G_a$ 的前缀和。

2. 从求和推广到乘积

Q13

P3704 [SDOI2017] 数字表格
共 $T\le10^3$ 组询问，且 $n,m\le10^6$。表格中第 $(i,j)$ 个位置为 Fibonacci 数 $f_{\gcd(i,j)}$，求所有位置权值之积。

加法型【F1】寻找的是约数上的“和分解”。这里最终要求乘积，因此对应地寻找约数上的“乘积分解”。

定义 $g_n$ 满足 $\displaystyle f_n = \prod_{d\mid n}g_d$，利用乘法形式的 Möbius 反演可写成 $\displaystyle g_n = \prod_{d\mid n} f_d^{\mu(n/d)}$。当 $\mu(n/d)=-1$ 时，负指数表示模意义下的逆元，因此参与反演的 Fibonacci 数必须在模数下非零且可逆；本题的数据范围与模数保证了这一条件。

于是有 $\displaystyle f_{\gcd(i,j)} = \prod_{d\mid\gcd(i,j)}g_d$。最终计算幂时，底数非零，因此指数可以按费马小定理对模数减一取模。

交换乘积顺序：

$$\begin{aligned} Ans &= \prod_{i=1}^{n}\prod_{j=1}^{m} \prod_{d\mid\gcd(i,j)}g_d \\ &= \prod_{d=1}^{\min(n,m)} g_d^{ \left\lfloor n/d\right\rfloor \left\lfloor m/d\right\rfloor } \end{aligned}$$

这里仍然是在统计“每个 $d$ 同时整除多少对 $(i,j)$”，只是最终聚合从加法变成了乘法。

---

八、统一认识

数论求和题可以优先沿下面的顺序分析：

1. 若要求 $\gcd(i,j)=k$，先整体除去 $k$，把问题化成互质计数；
2. 若 GCD 只需要属于某个集合，可以先枚举合法 GCD，复杂度不够时再合并这些贡献；
3. 若被加数就是 GCD，直接尝试【E1】；
4. 若被加数是一般的 $F(\gcd)$，直接尝试【F1】；
5. 若 GCD 外还有 $i,j$ 的额外权值，判断代换以后能否把这些权值分离；
6. 若原函数不是 $F(\gcd)$ 型，就寻找新的卷积恒等式；
7. 公式推完以后，再考虑【B1】、线性筛、杜教筛或离线数据结构。

整体推理思路链大致如下：

展开 → 交换求和顺序 → 代换 / 合并指标 → 分离变量 → 处理算术函数前缀和。