除数求和函数 \(\text{Divisor Summatory Function}\) 定义为
\[T(n)=\sum_{i=1}^n\left\lfloor\dfrac ni\right\rfloor \]非常简单吧 。
后面讨论的均为多组询问 。
记号约定：\((f(n))−O(g(n))\) 表示 \(O(f(n))\) 复杂度预处理，\(O(g(n))\) 复杂度询问 。
Algorithm -1：暴力，\(O(1)−O(n)\) .
Algorithm 0：每次整除分块，\(O(1)−O(√n)\) .
Algorithm 1：O(n) 递推，\(O(n)−O(1)\) .
考虑推下式子：
\[\sum\limits_{i=0}^{n}x\bmod i=nx-\sum\limits_{i=1}^{n}i\left\lfloor\frac{x}{i}\right\rfloor \]接下来考虑差分：
所以
线性筛出
σ(i) 的前缀和即可。