一些特殊的数论函数前缀和卡常技巧

约数个数前缀和

\( \begin{aligned}F(n)&=\sum\limits_{i=1}^n\sum\limits_{j|i}1\&=\sum\limits_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor\&=\sum\limits_{ij\le n}1\&=2\sum\limits_{i=1}^{\left\lfloor\sqrt n\right\rfloor}i\left\lfloor\frac{n}{i}\right\rfloor-\left\lfloor\sqrt n\right\rfloor^2 \end{aligned}\)

约数和前缀和

\(F(n)=\sum\limits_{i=1}^n\sum\limits_{j|i}j\)
这个东西等价于在\(x\in [1,n]\)时\(y=\frac{1}{x}\)曲线下所有整点的纵坐标之和。
枚举\(i,j\)中较小的一个
\(F(n)=\sum\limits_{i=1}^{\left\lfloor\sqrt n\right\rfloor}i(\left\lfloor\frac{n}{i}\right\rfloor-i)+\sum\limits_{j=i}^nj\)

已知质数幂处点值的狄利克雷卷积

\(F=G\times H\)

可以发现\(H=\prod_{p\in prime}H_p\)

那么可以对每个\(G_p\)拆开，单独与\(F\)做狄利克雷乘法。

一些特殊的数论函数前缀和卡常技巧

原文：https://www.cnblogs.com/bestlxm/p/13057690.html