这篇文章是上了 \(\rm yyc\) 的课之后得到的一些心得和总结。
高维点视角下的整除关系：
我们可以将一个数 \(x\) 唯一分解为 \(\prod_{i = 1}^{+\infty}p_i^{x_i}\) 的形式（其中 \(p_i\) 都是素数）。注意到每一种素数互不干扰，于是可以把每一种不同的素数看成立体空间的一维，把 \(x\) 看做一个高维点 \(p_x = (x_1, x_2, ....)\)。
从而有： \(m | n \Leftrightarrow \forall i, m_i \le n_i\)，即 \(p_m \le p_n\)。（注意这里比较的是偏序关系）。
接下来我们定义函数 \(f\) 的约数求和形式：
\[(\operatorname{Lsum}(f))(n) = \sum_{d|n}f(d) = \sum_{p_d \le p_n} f(d) \]注意到这个求和式的本质实际上是高位前缀和，于是我们可以依次考虑每一维并对每一维分别做前缀和。这样就做到 \(O(n \log \log n)\) 求和了。
同样的，我们定义倍数求和 \((\operatorname{Rsum}(f))(n) = \sum_{n | d}f(d) = \sum_{p_n \le p_d} f(d)\)。
有前缀和，自然我们就会考虑差分。定义 \(f\) 的约数差分为：
\[(\operatorname{Lsum}(\operatorname{Ldif}(f)))(n) = f(n) \]即前缀和的逆操作，倍数差分定义也是相同的。但是有这个定义式我们不足以了解约数差分函数的具体情况。容易发现 \(\operatorname{Ldif} * \operatorname{I} = f\)，从而 \(\operatorname{Lidf} = f * \mu\)。
从而倍数差分也不难联想到是 \(\operatorname{Rdif}(n) = \sum_{n | d} \mu(d)f(\frac{d}{n})\)，这个带入证明即可。
Luogu2714 四元组统计
“如果你还慢慢推式子，那你就输了。”
记 \(x\) 在 \(a\) 中出现的次数为 \(cnt_x\)。先做一遍倍数求和得到 \(\operatorname{Rsum}\)。那么对于一个 \(x\)，四个数都是 \(x\) 的倍数的四元组个数为 \(C_{cnt_x}^4\)。
在做一遍倍数差分，答案是 \(\operatorname{Rdif}(1)\)，没了。。。
标签：le,函数,数论,sum,差分,求和,倍数,operatorname,小记 From： https://www.cnblogs.com/little-corn/p/18348948