积性函数专题 #

例题 #

2.1 因数倍数素数相关 #

LG P1414 又是毕业季II #

给定一个 $n$ 元数组 $a_i$, 问对正整数 $k$ 从 $1$ 取到 $n$，从 $a_i$ 中选择 $k$ 个数的最大 $gcd$ 为多少 $1 \leq n \leq 10^4, 1 \leq a_i \leq 10^6$

• 调和级数枚举

CF757 div2 D1/2. Divan and Kostomuksha(E/H) #

给定一个 $n$ 元数组 $a_i$，对数组进行重排，使得下面表达式值最大，输出最大值 $$\sum_{i = 1}^ngcd(a_1, a_2, \cdots, a_i)$$

$1 \leq n \leq 10^5, 1 \leq a_i \leq 2 \times 10^7$(Easy中 $a_i \leq 5 \times 10^6$)

• 很像 LG1414 的问题，首先我们先获取值域每个数字倍数的个数 $b_i$
• 那么假若全部都是 $i$ 倍数，一个基础值就是 $i \cdot b_i$
• 但是 $i$ 倍数可能在前面一部分构成更大的一部分值，但注意到只有可能是 $i$ 的倍数，所以我们可以倒着遍历并枚举倍数，更新当前最大值，注意到最终答案就是 $b_1$
• 不进行优化的复杂度基于调和级数 $O(VlogV)$($V$ 是值域)，但这对于 Hard Version 是不可接受的，我们可以使用狄利克雷后缀和优化，计算 $b_i$ 是直接的，对于优化这个更新步骤我们可以使用类似的思想，只考虑素数倍数更新，最终复杂度 $O(n + VloglogV)$

2.2 积性函数 #

NC 华华给月月出题 #

给定 $n$ 计算下面的表达式

$$\bigoplus_{i = 1}^n(i^n mod (10^9 + 7))$$

$1 \leq n \leq 1.3 \times 10^7$

事实上这里 $n$ 的范围意味着直接进行枚举计算时间复杂度 $O(nlogn)$ 是不可接受的，这里我们可以使用线性筛 $O(n)$ 预处理 $1 - n$ 的 $n$ 次方

CF391 div1 + 2 E. Bash Plays with Functions #

牛客同题连接

按照下面的方式定义函数 $f_r(n)$

• 当 $r = 0$ 时， $$f_0(n) = \sum_{pq = n}[gcd(p, q) = 1]$$

即满足 $pq = n$ 且 $gcd(p, q) = 1$ 的有序对 $<p, q>$ 的对数

• 当 $r \geq 1$ 时 $$f_r(n) = \sum_{uv = n}\frac{f_{r-1}(u) + f_{r-1}(v)}{2}$$

$q$ 次查询，每次查询给定 $r, n$ 计算 $f_r(n)$ 的值 $1 \leq q, n, r \leq 10^6$

我们需要挖掘出如下的一些性质

1. $f_0(n) = 2^{\omega(n)}$ 是一个积性函数，这可以从标准质因数分解式中看出
2. $f_r(n) = \sum_{d \mid n}f_{r-1}(d)$ 即 $f_r$ 是 $f_{r-1}$ 的狄利克雷前缀和或者是莫比乌斯变换结果，所以 $f_r$ 也是积性函数

于是我们在计算 $f_r(n)$ 的时候，可以考虑分解为若干质因数幂次的乘积，下面我们只需要研究素数幂处的取值 $f_r(p^\alpha)$

首先对于 $f_0(p^\alpha)$，显然当 $\alpha = 0$ 即 $f_0(1) = 1$，当 $\alpha \geq 1$ 时，$f_0(p^\alpha) = 2$ 对于素数幂处的狄利克雷前缀和，取值显然和素数取值无关，考虑以指数 $\alpha$ 为下标，$r$ 阶函数即为 $r - 1$ 阶前缀和，即有如下关系 $$f_r(p^\alpha) = \sum_{i = 0}^\alpha f_{r - 1}(p^i)$$

对于常数函数的 $r(r > 0)$ 重前缀和，我们有组合数结论，则 $$f_r(p^\alpha) = 2\binom{r + \alpha - 1}{r} + \binom{r + \alpha}{r - 1}$$

预处理 $minp(n)$ 和组合数，可以实现 $O(n + r + qlogn)$ 时间复杂度

P2158 [SDOI2008] 仪仗队 #

转化题意，也就是给定 $n$，计算下面的表达式 $$\sum_{i = 0}^{n - 1}\sum_{j = 0}^{n - 1}[gcd(i, j) = 1]$$

$1 \leq n \leq 4 \times 10^4$

2.3 莫比乌斯反演 #

LG P3455 [POI 2007] ZAP-Queries #

SC同题链接 SC141

给出 $a, b, d$，求满足 $1 \leq x \leq a, 1 \leq y \leq b$，且 $gcd(x, y) = k$ 的二元组 $(x,y)$ 的数量 即求下面表达式的值

$$\sum_{i = 1}^n\sum_{j = 1}^m[gcd(i, j) = k]$$

$1 \leq T \leq 5 \times 10^4$ 组测试，$1 \leq n, m \leq 5 \times 10^4$

变形过程: $$\begin{aligned} \sum_{i = 1}^n\sum_{j = 1}^m[gcd(i, j) = k] &= \sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor}[gcd(i, j) = 1] \ &= \sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor}\sum_{d \mid gcd(i, j)}\mu(d) \ &= \sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor}\sum_{d \mid n \text{且} d \mid m}\mu(d) \ &= \sum_{d = 1}^{min(\lfloor \frac{n}{k} \rfloor, \lfloor \frac{m}{k} \rfloor)}\mu(d)\sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor}[d \mid i]\sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor}[d \mid j] \ &= \sum_{d = 1}^{min(\lfloor \frac{n}{k} \rfloor, \lfloor \frac{m}{k} \rfloor)}\mu(d)\lfloor \frac{\lfloor \frac{n}{k} \rfloor}{d} \rfloor \lfloor\frac{\lfloor \frac{n}{k} \rfloor}{d} \rfloor \ &= \sum_{d = 1}^{min(\lfloor \frac{n}{k} \rfloor, \lfloor \frac{m}{k} \rfloor)}\mu(d)\lfloor \frac{n}{kd} \rfloor \lfloor\frac{m}{kd} \rfloor \end{aligned}$$

• (1) 是压缩区间的技巧
• (2) 是莫比乌斯反演
• (3) 是最大公因数的本质属性，消除掉 $gcd$
• (4) 是求和换序
• (6) 是高斯函数的一个性质
• 预处理莫比乌斯函数及其前缀和，可以利用整数分块在 $O(V + T\sqrt{min(n, m)})$ 的时间内解决最终的求和式

LG P2522 [HAOI2011] Problem b #

给定 $a, b, c, d, k$ 求下面表达式的值

$$\sum_{i = a}^b\sum_{j = c}^d[gcd(i, j) = k]$$

$1 \leq T \leq 5 \times 10^4$ 组测试，$1 \leq a \leq b \leq 5 \times 10^4, 1 \leq c \leq d \leq 5 \times 10^4$

• 在上一题基础上做一个小容斥即可，设上一题中的求值函数是 $f(x, y, k)$ $$ans = f(b, d, k) - f(a, d, k) - f(b, c, k) + f(a, c, k)$$

SC 公约数之和 145 #

给定 $n$，求

$$\sum_{i=1}^n \sum_{j=i + 1}^n \gcd(i, j)$$

$1 \leq T \leq 1000$ 组测试样例，$1 \leq n \leq 10^6$

我们首先解决下面两个弱化板的题目：

弱化版_2 LG P2398 GCD SUM 弱化板_1 P1390 公约数的和

他们只需要处理单测，$n$ 的范围略不同但不影响做法

首先这三个题目求的式子是同一回事，注意到以下变形技巧 $$\sum_{i = 1}^n \sum_{j = 1}^n \gcd(i, j) = \frac{n(n + 1)}{2} + 2\sum_{i=1}^n \sum_{j = i + 1}^n \gcd(i, j)$$

所以我们只研究 $$\sum_{i=1}^n \sum_{j=1}^n \gcd(i, j)$$

的求法，在不考虑莫比乌斯反演的情况下，弱化版有更简单的做法，可以做如下变形：

$$\begin{aligned} \sum_{i = 1}^n \sum_{j = 1}^n gcd(i, j) &= \sum_{d = 1}^n d \sum_{i = 1}^n \sum_{j = 1}^n [gcd(i, j) = d] \ &= \sum_{d = 1}^n d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor}[gcd(i, j) = 1] \ &= \sum_{d = 1}^n d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}(2\sum_{j = 1}^{i}[gcd(i, j) = 1] - 1) \ &= \sum_{d = 1}^n d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}(2\phi(i) - 1) \end{aligned}$$

• (7) 是一个常见的提取技巧，转换求和顺序先枚举公因数，这个变形在后面经常用到，你会注意到这样提取出了艾佛森括号，便可以使用莫比乌斯反演（后面会用到）
• (8) 同(1)
• (9) 利用对称性，使得可以使用欧拉函数定义
• (10) 欧拉函数定义，注意到只有当两个界都是 $n$ 时才可以这样做，一般的给定上界 $n, m$ 也就不能有这个取巧的做法
• 于是可以预处理欧拉函数前缀和，$O(n)$ 的时间解决这个问题

题解还发现了一个调和级数枚举的方法，时间复杂度 $O(nlogn)$ 做法也挺神秘的

但是你会发现当我们需要多次查询时(结束这个弱化问题，回到原题)，这个办法时间复杂度 $O(Tn)$ 是不可接受的，这说明原式存在更快的做法

对于 (8) 式，我们可以使用莫比乌斯反演

$$\begin{aligned} \sum_{d = 1}^n d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor}[gcd(i, j) = 1] &= \sum_{d = 1}^n d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{d^{'} \mid gcd(i, j)}\mu(d^{'}) \ &= \sum_{d = 1}^n d \sum_{d^{'} = 1}^{\lfloor \frac{n}{d} \rfloor} \mu(d^{'}) \lfloor \frac{n}{dd^{'}} \rfloor^2 \ &= \sum_{t = 1}^n \lfloor \frac{n}{t} \rfloor^2 \sum_{d \mid t} d \mu(\frac{n}{d})(令 t = dd^{'}) \ &= \sum_{t = 1}^n \phi(t) \lfloor \frac{n}{t}\rfloor^2 \end{aligned}$$

• (11)和(12) 本质就是(1)到(6)的变形，我们省略

• (13) 是一个新技巧，我们合并两个变量再调换求和顺序，先枚举新变量再枚举一个旧变量，注意这里两个旧变量都是一样的，即(13)式等价于 $$\sum_{t = 1}^n \lfloor \frac{n}{t}\rfloor^2 \sum_{d^{'} \mid t} \frac{n}{d^{'}} \mu(d^{'})$$

• (14) 是关于欧拉函数的一个莫比乌斯反演公式，前面总结过

• 于是对于 (14) 式，可以预处理欧拉函数前缀和，然后利用整除分块可以做到 $O(n + T\sqrt n)$ 的时间复杂度

题解还有一种直接使用欧拉反演的推导，本质也就是在莫比乌斯反演的推论，不过需要的推导少一点

$$\begin{aligned} \sum_{i = 1}^n \sum_{j = 1}^n gcd(i, j) &= \sum_{i = 1}^n \sum_{j = 1}^n \sum_{d | gcd(i, j)} \phi(d) \ &= \sum_{d = 1}^n \phi(d) \sum_{i = 1}^n [d \mid i] \sum_{j = 1}^n [d \mid j] \ &= \sum_{d = 1}^n \phi(d) \lfloor \frac{n}{d}\rfloor^2 \end{aligned}$$

总结一点，莫比乌斯反演的方式具有更广的用法，这里的两个上界替换成不同数字 $n, m$ 也是可做的

LG P2257 YY的GCD #

给定 N,M，求 $1 \leq x \leq N，1 \leq y \leq M$ 且 $gcd(x,y)$ 为质数的 $(x,y)$ 有多少对

$T \leq 10^4$ 组测试, $1 \leq N, M \leq 10^7$

首先容易发现这个题和前几个题的区别是将答案范围限制在了质数上，我们同样考虑做一些代数变形

$$\begin{aligned} \sum_{i = 1}^N\sum_{j = 1}^M[gcd(i, j) \in Prime] &= \sum_{p \in Prime}\sum_{i = 1}^N\sum_{j = 1}^M[gcd(i, j) = p] \ &= \sum_{p \in Prime} \sum_{d = 1}^{min(\lfloor \frac{n}{p} \rfloor, \lfloor \frac{m}{p} \rfloor)} \lfloor \frac{n}{pd} \rfloor \lfloor \frac{m}{pd} \rfloor \ &= \sum_{t = 1}^{min(n, m)} \lfloor \frac{n}{t} \rfloor \lfloor \frac{m}{t} \rfloor \sum_{p \mid t} \mu(\frac{t}{p}) (令 t = pd) \end{aligned}$$

• (19) 本质就是(1)到(6)的变形，我们省略
• (20) 同(13)换元换序的技巧
• 于是我们预处理这样一个东西：$f(n) = \sum_{p|n}\mu(\frac{n}{p})$，一种初始化时间复杂度 $O(VlnlnV + T(\sqrt{M} + \sqrt{N}))$,其中 $V = 10^7$ 为预处理部分(埃式筛初始化)
• 事实上也可以线性筛初始化，这样初始化部分就是 $O(V)$

总结一个点

莫比乌斯反演的一个常见题目题型就为下面这个形式：

$$\sum_{i = 1}^{n}\sum_{j = 1}^{m}f(gcd(i, j))$$

我们可以一般化这个代数变形过程 $$\begin{aligned} \sum_{i = 1}^{n}\sum_{j = 1}^{m}f(gcd(i, j)) &= \sum_{d = 1}^{min(n, m)}\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} f(d)[gcd(i, j) = 1] \ &= \sum_{d = 1}^{min(n, m)}f(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} \sum_{d^{'} \mid gcd(i, j)}\mu(d^{'}) \ &= \sum_{d = 1}^{min(n, m)}f(d) \sum_{d^{'} \mid gcd(i, j)}\mu(d^{'})\lfloor \frac{n}{dd^{'}} \rfloor \lfloor \frac{m}{dd^{'}} \rfloor \ &= \sum_{t = 1}^{min(n, m)} \lfloor \frac{n}{t} \rfloor \lfloor \frac{m}{t} \rfloor \sum_{d \mid t}\mu(\frac{t}{d}) f(d) \ &= \sum_{t = 1}^{min(n, m)} \lfloor \frac{n}{t} \rfloor \lfloor \frac{m}{t} \rfloor g(t);(g = f * \mu) \end{aligned}$$

• 上述所有代数变形都是出现过的，当然这个式子局限性很大，要求右边函数是关于 $gcd$ 的单变量函数

LG P3768 简单的数学题 #

给定 $n, p$，计算下面表达式的值 $$(\sum_{i = 1}^n\sum_{j = 1}^nijgcd(i, j))(mod:p)$$

$1 \leq n \leq 10^{10}, 5 \times 10^8 \leq p \leq 1.1 \times 10^9$

变形的要点我们之前都已经讲过 $$\begin{aligned} \sum_{i = 1}^n\sum_{j = 1}^nijgcd(i, j) &= \sum_{i = 1}^n\sum_{j = 1}^nij\sum_{d \mid gcd(i, j)}\phi(d) \ &= \sum_{d = 1}^n\phi(d)(\sum_{i = 1}^ni[i \mid d])^2 \ &= \sum_{d = 1}^n\frac{1}{4}d^2\phi(d)(\lfloor \frac{n}{d} \rfloor(1 + \lfloor \frac{n}{d} \rfloor))^2 \end{aligned}$$

于是我们需要计算 $\sum_{i = l}^ri^2\phi(i)$ 即需要 $i^2\phi(i)$ 的前缀和之后进行整除分块，这个前缀和需要进行杜教筛

LG P3312 [SDOI2014] 数表 #

$T$ 次询问，每次询问给定 $n, m, a$ 计算下面表达式的值 $$\sum_{i = 1}^n\sum_{j = 1}^m\sigma(gcd(i, j))[\sigma(gcd(i, j)) \leq a]$$

$1 \leq T \leq 2 \times 10^4, 1 \leq n, m \leq 10^5$

代数变形的部分我们略写 $$\begin{aligned} &\sum_{i = 1}^n\sum_{j = 1}^m\sigma(gcd(i, j))[\sigma(gcd(i, j)) \leq a] \ &= \sum_{d = 1}^{min(n, m)}\sigma(d)[\sigma(d) \leq a]\sum_{i = 1}^n\sum_{j = 1}^m[gcd(i, j) = d] \ &= \sum_{t = 1}^{min(n, m)}\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor\sum_{d \mid t}\sigma(d)\mu(\frac{t}{d})[\sigma(d)\leq a] \end{aligned}$$

我们注意到若没有 $a$ 的限制，这个问题在预处理 $\sigma * \mu(n)$ 这个积性函数及其前缀和后每次查询进行数论分块基于可以，但是加上这个限制我们发现有的 $d$ 就不会考虑，怎么办呢？

我们这里需要结合到数据结构的思想，我们对查询进行离线，考虑对 $a$ 递增的维护 $\sigma * \mu(n)$ 这个积性函数及其前缀和，每次更新需要对 $d$ 及其倍数下标累加上 $\sigma * \mu(d)$ 这样的更新均摊下来就是讲调和级数的预处理分散到了各个查询。另外，由于需要动态维护前缀和，我们需要使用树状数组，最终的时间复杂度 $O(q\sqrt{n}logn + nlog^2n)$（认为 $n$ 和 $m$ 同阶）

SPOJ LCMSUM #

洛谷rj题面

给定 $n$，计算下面的值 $$\sum_{i = 1}^n lcm(i, n)$$

$1 \leq T \leq 3 \times 10^5$ 组样例，$1 \leq n \leq 10^6$

初见 $lcm$，根据化归思想我们容易想到变形成关于 $gcd$ 的式子，不过接下来从莫反角度就有点无从下手，不过题解给出了一种神秘的变形做法，无需莫反（不知道有没有别的做法啊）

$$\begin{aligned} \sum_{i = 1}^n lcm(i, n) &= \sum_{i = 1}^n \frac{in}{gcd(i, n)} \ &= n + \frac{1}{2}(\sum_{i = 1}^{n - 1}\frac{in}{gcd(i, n)} + \frac{(n - i)n}{gcd(n - i, n)}) \ &= n + \frac{1}{2}\sum_{i = 1}^{n - 1}\frac{n^2}{gcd(i, n)} \ &= \frac{1}{2}n + \frac{1}{2}n^2\sum_{i = 1}^{n}\frac{1}{gcd(i, n)} \ &= \frac{1}{2}n + \frac{1}{2}n^2\sum_{d \mid n}\frac{1}{d}\sum_{i = 1}^{n}[gcd(i, n) = d] \ &= \frac{1}{2}n + \frac{1}{2}n^2\sum_{d \mid n}\frac{1}{d}\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}[gcd(i, \frac{n}{d}) = 1] \ &= \frac{1}{2}n + \frac{1}{2}n^2\sum_{d \mid n}\frac{1}{d}\phi(\frac{n}{d}) \ &= \frac{1}{2}n(1 + \sum_{d \mid n}d\phi(d)) \end{aligned}$$

• (21) 是二元 $gcd$ 和 $lcm$ 的关系
• (22) 是一个利用对称性的变形，这个变形本身算是常见但感觉不太容易想到
• (23)(24) 是常规变形，值得注意的是 (24) 将求和上限恢复成 $n$ 是很有利于后面的变形的
• (25)(26) 是求和换序，从而在 (27) 转化出欧拉函数定义
• 于是可以预处理 $f(n) = \sum_{d \mid n}d\phi(d)$，在 $O(nlogn + T)$ 的时间解决问题
• 补充的一点是不进行 (24) 的变形也是可以的，本质相同但要注意 $d \neq n$

LG P1829 [国家集训队] Crash的数字表格 / JZPTAB #

给定 $n, m$，计算下面的值

$$\sum_{i = 1}^n\sum_{j = 1}^m lcm(i, j)$$

$1 \leq n, m \leq 10^7$

更加复杂一点的变形

$$\begin{aligned} \sum_{i = 1}^n\sum_{j = 1}^m lcm(i, j) &= \sum_{i = 1}^n\sum_{j = 1}^m\frac{ij}{gcd(i, j)} \ &= \sum_{d = 1}^{min(n, m)}\frac{1}{d}\sum_{i = 1}^n\sum_{j = 1}^m ij[gcd(i, j) = d] \ &= \sum_{d = 1}^{min(n, m)}d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} ij[gcd(i, j) = 1] \ &= \sum_{d = 1}^{min(n, m)}d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} ij\sum_{d' \mid gcd(i, j)}\mu(d') \ &= \sum_{d = 1}^{min(n, m)}d\sum_{d' = 1}^{min(\lfloor \frac{n}{d} \rfloor, \lfloor \frac{m}{d} \rfloor)} \mu(d')\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}i[d' \mid i]\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} j[d' \mid j] \ &= \sum_{d = 1}^{min(n, m)}d\sum_{d' = 1}^{min(\lfloor \frac{n}{d} \rfloor, \lfloor \frac{m}{d} \rfloor)}d'^2\mu(d') \frac{\lfloor \frac{n}{dd'} \rfloor(\lfloor \frac{n}{dd'} \rfloor + 1)}{2}\frac{\lfloor \frac{m}{dd'} \rfloor(\lfloor \frac{m}{dd'} \rfloor + 1)}{2} \ &= \sum_{t = 1}^{min(n, m)}\frac{\lfloor \frac{n}{t} \rfloor(\lfloor \frac{n}{t} \rfloor + 1)}{2}\frac{\lfloor \frac{m}{t} \rfloor(\lfloor \frac{m}{t} \rfloor + 1)}{2}t\sum_{d' \mid t} d'\mu(d')(令t = dd') \end{aligned}$$

• (31) 需要注意 $i, j$ 除以 $d$ 后前面多乘上了 $d^2$
• (34) 需要注意不要漏了 $d'^2$，这里存在一个等差数列求和式
• 需要指出的是，这个变形是我自己给出的，预处理 $f(t) = \sum_{d' \mid t} d'\mu(d')$ 后 (35)式 数论分块可以做到 $O(\sqrt{min(n, m)})$ 的时间求值，但这个题没有多测，存在其他很多 $O(min(n, m))$ 的方法就已经足够了
• 具体而言 $O(min(n, m))$ 的方法是只进行到 (34)式，令 $$h(n, m) = \sum_{d' = 1}^{min(n, m)}d'^2\mu(d') \frac{\lfloor \frac{n}{d'} \rfloor(\lfloor \frac{n}{d'} \rfloor + 1)}{2}\frac{\lfloor \frac{m}{d'} \rfloor(\lfloor \frac{m}{d'} \rfloor + 1)}{2}$$

从而 $$ans = \sum_{d = 1}^{min(n, m)}dh(\lfloor \frac{n}{d} \rfloor, \lfloor \frac{m}{d} \rfloor)$$

在计算答案时，预处理 $d^2\mu(d)$ 的前缀和，单个 $h(n, m)$ 的计算可以数论分块，计算 $ans$ 时数论分块，总计就是 $O(min(n, m))$ 的时间

• 使用更加优秀的 (35)式计算时，则需要预处理 $f(t) = \sum_{d' \mid t} d'\mu(d')$ 显然能够 $O(nlogn)$ 调和级数的预处理，但是对于 $10^7$ 自然会超时，注意到这是一个积性函数，可以使用线性筛 $O(n)$ 预处理，或者使用狄利克雷前缀和 $O(nloglogn)$ 预处理
• 关于为什么是积性函数，题解给出了一个巧妙的观点 $t\sum_{d' \mid t} d'\mu(d') = \sum_{d' \mid t} d'^2\mu(d')\frac{t}{d'} = (t^2\mu(t)) * t$，本质是(34)式到(35)式不化简，从狄利克雷卷积的角度这必然是积性函数

hdu4944 FSF’s game #

给定 $n$，计算下面的值

$$\sum_{i = 1}^n\sum_{j = i}^n\sum_{d \mid i, j} \frac{ij}{gcd(\frac{i}{d}, \frac{j}{d})}$$

$1 \leq T \leq 5 \times 10^5$ 组测试，$1 \leq n \leq 5 \times 10^5$

这是一个更为综合的题目

我起初的推导 #

下面首先给出我之前给出的推导，由 $gcd$ 的性质我们知道

$$\sum_{i = 1}^n\sum_{j = i}^n\sum_{d \mid i, j} \frac{ij}{gcd(\frac{i}{d}, \frac{j}{d})} = \sum_{i = 1}^n\sum_{j = i}^n\sum_{d \mid i, j} \frac{ijd}{gcd(i, j)}$$

而下标从 $i$ 开始是我们不喜欢的，可以做一个转化

$$\sum_{i = 1}^n\sum_{j = i}^n\sum_{d \mid i, j} \frac{ijd}{gcd(i, j)} = \frac{1}{2}(\sum_{i = 1}^n\sum_{j = 1}^n\sum_{d \mid i, j} \frac{ijd}{gcd(i, j)} + \sum_{i = 1}^{n}i\sigma(i))$$

接下来我们就只考虑

$$\sum_{i = 1}^n\sum_{j = 1}^n\sum_{d \mid i, j} \frac{ijd}{gcd(i, j)}$$

进行类似前几题的变形

$$\begin{aligned} \sum_{i = 1}^n\sum_{j = 1}^n\sum_{d \mid i, j} \frac{ijd}{gcd(i, j)} &= \sum_{k = 1}^n\frac{1}{k}\sum_{i = 1}^n\sum_{j = 1}^nij[gcd(i, j) = k]\sum_{d \mid k}d \ &= \sum_{k = 1}^nk\sigma(k)\sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j = 1}^{\lfloor \frac{n}{k} \rfloor}ij[gcd(i, j) = 1] \ &= \sum_{k = 1}^nk\sigma(k)\sum_{d = 1}^{\lfloor \frac{n}{k} \rfloor}\mu(d)\sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor}i[d \mid i]\sum_{j = 1}^{\lfloor \frac{n}{k} \rfloor}j[d \mid j] \ &= \sum_{k = 1}^nk\sigma(k)\sum_{d = 1}^{\lfloor \frac{n}{k} \rfloor}\mu(d)d^2 (\frac{\lfloor \frac{n}{kd} \rfloor (1 + {\lfloor \frac{n}{kd} \rfloor})}{2})^2 \ &= \sum_{t = 1}^n (\frac{\lfloor \frac{n}{t} \rfloor (1 + {\lfloor \frac{n}{t} \rfloor})}{2})^2t \sum_{d \mid t}d\mu(d)\sigma(\frac{t}{d}) \end{aligned}$$

• (36) 是求和换序，枚举 $gcd$，同时 $d$ 就会与 $i, j$ 独立
• (37) 在转换 $i, j$ 的同时消除掉 $d$
• (38)(39)(40) 的变形同前
• 于是我们预处理 $n\sigma(n)$ 和 $\sum_{d \mid n}d\mu(d)\sigma(\frac{n}{d})$，可以在 $O(nlogn + T\sqrt n)$ 的时间内解决这个问题，但是你会发现这样 $T$ 了。$hdu$ 的机子还是太慢了 $3.5 \times 10^8$ 竟然 $4.5s$ 跑不过

博客思路 #

首先

$$\begin{aligned} \sum_{i = 1}^n\sum_{j = i}^n\sum_{d \mid i, j} \frac{ij}{gcd(\frac{i}{d}, \frac{j}{d})} &= \sum_{i = 1}^n\sum_{j = i}^n\sum_{d \mid i, j} \frac{ijd}{gcd(i, j)} &= \sum_{i = 1}^n\sum_{j = i}^n\sum_{d \mid i, j} d:lcm(i, j) \end{aligned}$$

注意到转化为有关 $lcm$ 的式子，我们朝着前两个题的方向进行

$$\begin{aligned} \sum_{i = 1}^n\sum_{j = i}^n\sum_{d \mid i, j} d:lcm(i, j) &= \sum_{d = 1}^nd\sum_{i = 1}^n\sum_{j = i}^nlcm(i, j)[d \mid i 且 d \mid j] \ &= \sum_{d = 1}^nd^2\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = i}^{\lfloor \frac{n}{d} \rfloor}lcm(i, j) \end{aligned}$$

我们定义 $s(n) = \sum_{i = 1}^n\sum_{j = 1}^nlcm(i, j)$ 这恰好是上一个题，在 $n = m$ 下的特殊情况

思路一

在上一个题中，我们给出了在 $O(n)$ 预处理，$O(\sqrt n)$求单个 $s(n)$ 的最快方法，但这样在外层同时进行数论分块的情况下时间复杂度是 $O(Tn)$ 更加无法通过

思路二

注意这里是上一个题 $n = m$ 的特殊情况，在这种情况下有其他的方法，我们在上上个题中，计算 $$\sum_{i = 1}^n lcm(i, n)$$

存在 $O(1)$ 的查询方法，我们注意到下面这一点 $$s(n) - s(n - 1) = \sum_{i = 1}^n lcm(i, n)$$

从而 $s(n)$ 即可前缀和直接求出，于是在外层数论分块的情况下有 $O(T\sqrt n)$ 的做法，也无法通过。

我们得到了同样复杂度的成果，但是接下来呢，我们期望实现 $O(1)$ 的查询，那么也就是说答案数组 $ans_i$ 是可以预处理出来的，我们注意到 $$ans_n = \sum_{d = 1}^nd^2s(\lfloor \frac{n}{d} \rfloor)$$

倘若我们枚举变量 $d$，那么 $\lfloor \frac{i}{d} \rfloor$ 天然被分成 $\lfloor \frac{n}{d} \rfloor$ 块，我们接着枚举每一个块做差分，最后做前缀和就可以在 $O(nlogn)$ 的时间内预处理好 $ans_i$，从而可以实现 $O(1)$ 查询。最终复杂度 $O(nlogn + T)$

不知道的我的做法能不能继续优化

loj 2185「SDOI2015」约数个数和 #

洛谷同题链接LG P3327

给定 $n, m$，计算下面的值

$$\sum_{i = 1}^n\sum_{j = 1}^md(ij)$$

$1 \leq T \leq 5 \times 10^4$ 组测试，$1 \leq n, m \leq 5 \times 10^4$

第一次遇到 $d(ij)$ 我们还是希望化归到 $gcd(i, j)$ 的形式，所以我们给出如下的引理 $$d(ij) = \sum_{x \mid i}\sum_{y \mid j}[gcd(x, y) = 1]$$

可以使用构造双射或者直接在素因子分解式上考虑因数个数公式证明，于是我们可以做如下的变形 $$\begin{aligned} \sum_{i = 1}^n\sum_{j = 1}^md(ij) &= \sum_{i = 1}^n\sum_{j = 1}^m\sum_{x \mid i}\sum_{y \mid j}[gcd(x, y) = 1] \ &= \sum_{i = 1}^n\sum_{j = 1}^m\sum_{x \mid i}\sum_{y \mid j}\sum_{d \mid gcd(x, y)}\mu(d) \ &= \sum_{i = 1}^n\sum_{j = 1}^m\sum_{d \mid i, j}\mu(d)\sum_{x \mid i 且 d \mid x}\sum_{y \mid j 且 d \mid y} \ &= \sum_{i = 1}^n\sum_{j = 1}^m\sum_{d \mid i, j}\mu(d)d(\lfloor \frac{i}{d} \rfloor)d(\lfloor \frac{j}{d} \rfloor) \ &= \sum_{d \mid i, j}\mu(d)\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}d(i)\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}d(j) \end{aligned}$$

• (44) 到 (46) 是对 $x, y$ 关于 $d$ 换序，(47)是对 $i, j$ 关于 $d$ 换序
• 于是由 (47) 式，预处理 $d(n)$ 和 $\mu(n)$ 及其前缀和，可以在 $O(n + T\sqrt n)$ 的时间内解决

基于值域的反演一例 #

下面我们给两个在值域上进行莫比乌斯反演的例子

给定一个长为 $n$ 的数组 $a_i$，计算下面的值 $$\sum_{i = 1}^n\sum_{j = 1}^n(gcd(a_i, a_j) + [gcd(a_i, a_j) \neq 1])$$

既然出现了 $gcd$ 同样的我们先做如下变形

$$\begin{aligned} \sum_{i = 1}^n\sum_{j = 1}^n(gcd(a_i, a_j) + [gcd(a_i, a_j) \neq 1]) &= \sum_{i = 1}^n\sum_{j = 1}^n\sum_{d \mid gcd(a_i, a_j)}\phi(d) + n^2 - \sum_{i = 1}^n\sum_{j = 1}^n\sum_{d \mid gcd(a_i, a_j)}\mu(d) \ &= n^2 + \sum_{i = 1}^n\sum_{j = 1}^n\sum_{d \mid gcd(a_i, a_j)}(\phi(d) - \mu(d)) \ &= n^2 + \sum_{d = 1}^{min{a_i}}(\phi(d) - \mu(d))\sum_{i = 1}^n[d \mid a_i]\sum_{j = 1}^n[d \mid a_j] \end{aligned}$$

• 其中 (48) 式是讲非互质转化为互质，是比较自然的想法

我们定义 $cnt[x] = \sum_{i = 1}^n[x \mid a_i]$ 即数组中满足值为 $x$ 的倍数的数字个数，那么我们要求的结果就是 $$n^2 + \sum_{d = 1}^{min{a_i}}(\phi(d) - \mu(d))cnt^2(d)$$

所以我们预处理 $cnt(i)$ (调和级数枚举)即可在 $O(nlogn)$ 的时间得到（或者狄利克雷后缀和优化 $O(nloglogn)$）

NC练习赛104 炫酷反演魔术 #

给定一个长为 $n$ 的数组 $a_i$，计算下面的值 $$\sum_{i = 1}^n\sum_{j = 1}^n\phi(a_i, a_j^3)$$

$1 \leq n, a_i \leq 3 \times 10^5$

首先我们做变形

$$\begin{aligned} \sum_{i = 1}^n\sum_{j = 1}^n\phi(a_i, a_j^3) &= \sum_{d = 1}^{max{a_i}}\phi(d)\sum_{i = 1}^n\sum_{j = 1}^n[gcd(a_i, a_j^3) = d] \ &= \sum_{d = 1}^{max{a_i}}\phi(d)\sum_{i = 1}^n\sum_{j = 1}^n[d \mid a_i 且 d \mid a_j^3]\sum_{d' \mid gcd(\frac{a_i}{d}, \frac{a_j^3}{d})}\mu(d') \ &= \sum_{d = 1}^{max{a_i}}\phi(d)\sum_{d' = 1}^{max{\lfloor\frac{a_i}{d}\rfloor}}\mu(d')\sum_{i = 1}^n[dd' \mid a_i]\sum_{j = 1}^n[dd' \mid a_j^3] \ &= \sum_{t = 1}^{max{a_i}}(\sum_{i = 1}^n[t \mid a_i])(\sum_{j = 1}^n[t \mid a_j^3])\sum_{d \mid t}\phi(d)\mu(\frac{t}{d})(令 t = dd') \end{aligned}$$

• (51)(53) 是求和换序，(52) 是莫比乌斯反演，(54) 是前面多次见的换元

接下来我们类似的定义 $cnt(n) = \sum_{i = 1}^n[n \mid a_i]$，但接下来我们还有两个没见过的新东西

一个是 $\sum_{d \mid t}\phi(d)\mu(\frac{t}{d})$，熟悉的人也许能一下反映到这就是 $\mu * \phi(n)$，即莫比乌斯函数和欧拉函数的狄利克雷卷积，这个目前只能线性筛预处理

另一个是 $\sum_{j = 1}^n[t \mid a_j^3]$，我们考虑将 $t$ 做一个变换 $f(t)$，假设 $t = \prod_{i = 1}^sp_i^{\alpha_i}$，令 $f(t) = \prod_{i = 1}^sp_i^{\lfloor\frac{\alpha_i}{3}\rfloor}$，于是 $\sum_{j = 1}^n[t \mid a_j^3] = cnt(f(t))$，这里实际操作时需要分解质因数，需要预处理 $minp(i)$

综合上述过程，我们预处理 $\mu * \phi(i), cnt(i), f(i)$ 可以在 $O(blogn)$ 的时间解决这个问题