设 \(c_i\) 表示 \(i\) 在 \(A\) 中的出现次数 ， 即 \(c_i = \sum\limits_{j = 1} ^ N [A_j = i]\)，则
\[\begin{aligned}S& = \sum\limits_{i = 1} ^ N \sum\limits_{j = 1} ^ N \mathrm{lcm}(A_i, A_j) \\& = \sum\limits_{d = 1} ^ V \sum\limits_{i = 1} ^ N \sum\limits_{j = 1} ^ N \dfrac {A_iA_j} d [\gcd(A_i, A_j) = d] \\& = \sum\limits_{d = 1} ^ V \sum\limits_{i = 1} ^ V \sum\limits_{j = 1} ^ V \dfrac {ij c_i c_j} d [\gcd(i, j) = d] \\& = \sum\limits_{d = 1} ^ V d \sum\limits_{i = 1} ^ {\frac V d} \sum\limits_{j = 1} ^ {\frac V d} ij c_{id} c_{jd} [\gcd(i, j) = 1] \\& = \sum\limits_{d = 1} ^ V d \sum\limits_{d' = 1} ^ {\frac V d} \mu(d') d' ^ 2 \sum\limits_{i = 1} ^ {\frac V {dd'}} \sum\limits_{j = 1} ^ {\frac V {dd'}} ij c_{idd'} c_{jdd'} \\& = \sum\limits_{T = 1} ^ V \sum\limits_{d \mid T} \mu(d) d ^ 2 \frac T d \sum\limits_{i = 1} ^ {\frac V T} \sum\limits_{j = 1} ^ {\frac V T} ijc_{iT}c_{jT} \\& = \sum\limits_{T = 1} ^ V T f(T) g ^ 2(T)\end{aligned}\]其中 \(T = dd'\)，\(f(T) = \sum\limits_{d\mid T} \mu(d) d\) ， \(g(T) = \sum\limits_{i = 1} ^ {\frac V T} ic_{iT}\) 。\(f\) 容易线性筛预处理，\(g\) 可以枚举因数或狄利克雷后缀和 。时间复杂度 \(\mathcal{O}(V\log V)\) 或 \(\mathcal{O}(V\log\log V)\) 。代码 。
IX. P3911 最小公倍数之和双倍经验 。
X. P6156 简单题和上题一样的套路 。枚举 \(\gcd\) ， 再莫比乌斯反演，得
\[\sum\limits_{d = 1} ^ n d ^ {k + 1} \mu ^ 2(d) \sum\limits_{d' = 1} ^ {\frac n d} d' ^ k \mu(d') \sum\limits_{i = 1} ^ {\frac n {dd'}}\sum\limits_{j = 1} ^ {\frac n {dd'}} (i + j) ^ k\]令 \(T = dd'\)，得
\[\sum\limits_{T = 1} ^ n T ^ k \sum\limits_{d \mid T} d \mu ^ 2(d) \mu\left(\frac n d\right) \sum\limits_{i = 1} ^ {\frac n T}\sum\limits_{j = 1} ^ {\frac n T} (i + j) ^ k\]线性筛预处理出 \(f = (d\times \mu ^ 2) * \mu\) 的前缀和，并预处理自然数幂和求后面的东西 。整除分块求解上式，时间复杂度 \(\mathcal{O}(n\frac {\log k}{\log n})\) 。代码见下一题 。
XI. P6222 「P6156 简单题」加强版双倍经验 ， 时间复杂度 \(\mathcal{O}(n\frac {\log k}{\log n} + T\sqrt n)\) 。注意比较卡空间 。代码 。
XII. P3327 [SDOI2015] 约数个数和利用 5.4 小节的第二个公式，套入莫比乌斯反演，可得答案式
\[\sum\limits_{d = 1} ^ {\min(n, m)} \mu(d) \sum\limits_{x = 1} ^ {\frac n d} \sum\limits_{y = 1} ^ {\frac m d} \frac n {xd} \frac m {yd}\]整除分块预处理 \(g(n) = \sum\limits_{i = 1} ^ n \dfrac n i\)，则答案为 \(\sum\limits_{d = 1} ^ {\min(n, m)} \mu(d) g(\frac n d) g(\frac m d)\)，整除分块即可 。时间复杂度 \(\mathcal{O}((n + T)\sqrt n)\) 。代码 。
XIII. P1447 [NOI2010] 能量采集XIV. P6810 「MCOI-02」Convex Hull 凸包XV. P2158 [SDOI2008] 仪仗队XVI. P3704 [SDOI2017] 数字表格设 \(c = \min(n, m)\) 。
\[\begin{aligned}\mathrm{answer} & = \prod\limits_{i = 1} ^ n \prod\limits_{j = 1} ^ m f_{\gcd(i, j)} \\& = \prod\limits_{d = 1} ^ c f_d ^ {\sum_{i = 1} ^ n \sum_{j = 1} ^ m [\gcd(i, j) = d]} \\& = \prod\limits_{d = 1} ^ c f_d ^ {\sum_{d' = 1} ^ \frac c d \mu(d') \frac n {dd'} \frac m {dd'}} \\& = \prod\limits_{T = 1} ^ c \left(\prod\limits_{d\mid T} f_d ^ {\mu(\frac n d)} \right) ^ {\frac n T \frac m T}\end{aligned}\]线性或线对预处理 \(f\) 及其逆元，线对预处理 \(g(n) = \sum\limits_{d\mid n} f_d ^ {\mu(\frac n d)}\) 。对每组询问整除分块即可做到 \(\mathcal{O}(T\sqrt n\log n)\) 。
6. 杜教筛杜教筛可以在亚线性时间内求出满足条件的数论函数前缀和 。
6.1 算法介绍杜教筛公式的推导相当自然，但动机十分巧妙 。设希望求出 \(f\) 在 \(n\) 处的前缀和 \(s(n) = \sum\limits_{i = 1} ^ n f(i)\)，我们构造另一个数论函数 \(g\)，设 \(h = f * g\)，则
\[\begin{aligned}& \sum\limits_{i = 1} ^ n h(i) \\= \ & \sum\limits_{ij \leq n} f(i) g(j) \\= \ & \sum\limits_{d = 1} ^ n g(d) \sum\limits_{i = 1} ^ {\frac n d} f(i) \\= \ & \sum\limits_{d = 1} ^ n g(d) s\left(\left\lfloor\frac n d\right\rfloor\right)\end{aligned}\]这说明若 \(g, h\) 的前缀和可快速求出，我们就得到了 \(s(n)\) 关于其所有整除值处取值的递推式，即
\[g(1) s(n) = \sum\limits_{i = 1} ^ n h(i) - \sum\limits_{d = 2} ^ n g(d)s\left(\left\lfloor\frac n d\right\rfloor\right)\]一般可杜教筛函数 \(f\) 及其对应构造函数 \(g\) 均为积性函数，因此 \(g(1) = 1\)，公式又写为 。
\[s(n) = \sum\limits_{i = 1} ^ n h(i) - \sum\limits_{d = 2} ^ n g(d)s\left(\left\lfloor\frac n d\right\rfloor\right)\]另一种理解方式：设第一象限每个整点 \((x, y)\) 的权值为 \(f(y) g(x)\) 。想象反比例函数 \(y = \dfrac n x\)，它与 \(x, y\) 轴正半轴围成的区域内所有整点的权值和为 \(S = \sum\limits_{xy\leq n} f(y)g(x)\) 。当 \(x = 1\) 时，\(\sum\limits_{y = 1} ^ n f(y)\) 即 \(s(n)\) 贡献至 \(S\) 。当 \(x > 1\) 时，考虑一个横坐标区间 \([L, R](2\leq L\leq R\leq n)\) 。若对于任意 \(x\in [L, R]\) 满足 \(\left\lfloor\dfrac n x\right\rfloor\) 相等，即 \(\left\lfloor\dfrac n L\right\rfloor = \left\lfloor\dfrac n R\right\rfloor\)，则该横坐标区间所有产生贡献的点形成矩形 \([L, R] \times \left[1, \left\lfloor\dfrac n L\right\rfloor\right]\)，它们的权值和即 \(\left(\sum\limits_{x = L} ^ R g(x) \right) s\left(\dfrac n L\right)\) 。由于整除值数量为 \(\mathcal{O}(\sqrt n)\)，所以 \(S\) 可写为 \(\mathcal{O}(\sqrt n)\) 个矩形的和 。稍作变形即得 \(s(n)\) 的递推式 。
推荐阅读
- 前端程序员学习 Golang gin 框架实战笔记之一开始玩 gin
- 1 Libgdx游戏学习——环境配置及demo运行
- 苹果ipad分屏功能怎么使用（ipad 9可以分屏学习吗)
- Go设计模式学习准备——下载bilibili合集视频
- 学习ASP.NET Core Blazor编程系列五——列表页面
- 七 Netty 学习：NioEventLoop 对应线程的创建和启动源码说明
- ZCTF note3：一种新解法
- 学习ASP.NET Core Blazor编程系列四——迁移
- 五 Netty 学习：服务端启动核心流程源码说明
- 【前端必会】走进webpack生命周期，另类的学习方法