经验总结

  1. 首页 > 生活 > >

初等数论学习笔记 III：数论函数与筛法(11)

生活百科


\[\begin{aligned}& \sum\limits_{T = 1} ^ c S(T) \sum\limits_{e \mid T} \mu(e) e ^ 2 \frac T e \\& \sum\limits_{T = 1} ^ c S(T) T \sum\limits_{e \mid T} \mu(e) e \\\end{aligned}\]至此已经可以狄利克雷前缀和 \(c\log \log c\) 求解问题 。但注意到 \(\mu \cdot \mathrm{id}\) 是积性函数 ， 所以 \(f = 1 * (\mu \cdot \mathrm{id})\) 也是积性函数 ， 且其在质数幂处的取值可快速计算 ， 可线性筛 。则答案式化简为 \(\sum\limits_{i = 1} ^ c S(i)f(i)i\) ， 其中仅 \(S\) 与 \(n, m\) 有关 。同时注意到 \(S\) 仅涉及到 \(n, m\) 整除值处的等差数列求和 ， 因此求出 \(f(i) i\) 的前缀和后 ， 可整除分块 \(\mathrm{O}(\sqrt c)\) 求解答案 。
时间复杂度 \(\mathcal{O}(c + T\sqrt c)\) 。代码 。
VIII. AT5200 [AGC038C] LCMs令 \(S = \sum\limits_{i = 1} ^ N \sum\limits_{j = 1} ^ N \mathrm{lcm}(A_i, A_j)\) ， 则答案为 \(S\) 减去 \(A\) 的和之后除以 \(2\) 。问题转化为求 \(S\) 。
设 \(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)\) 。

经验总结扩展阅读


上一篇：2023年10月19日打猎吉日一览表 2023年10月19日打猎行吗

下一篇：2022年阴历11月提车最好的日子