$$
\begin {aligned}
ANS & = \sum _ {i = 1} ^ n \sum _ {j = 1} ^ m \sigma ((i, j)) [\sigma((i, j)) \le a] \\
& = \sum _ {i = 1} ^ n \sum _ {j = 1} ^ m \sum _ {d = 1} ^ n \sigma(d)[\sigma(d) \le a] [(i, j) = d] \\
& = \sum _ {d = 1} ^ n \sigma (d) [\sigma(d) \le a] \sum _ {i = 1} ^ {\lfloor \frac n d \rfloor} \sum _ {j = 1} ^ {\lfloor \frac n d \rfloor} [(i, j) = 1] \\
& = \sum _ {d = 1} ^ n \sigma (d) [\sigma(d) \le a] \sum _ {i = 1} ^ {\lfloor \frac n d \rfloor} \sum _ {j = 1} ^ {\lfloor \frac n d \rfloor} \sum _ {e | (i, j)} \mu(e) \\
& = \sum _ {d = 1} ^ n \sigma (d) [\sigma(d) \le a] \sum _ {e = 1} ^ n \mu(e) \sum _ {i = 1} ^ {\lfloor \frac n {de} \rfloor} \sum _ {j = 1} ^ {\lfloor \frac n {de} \rfloor} 1\\
& = \sum _ {T = 1} ^ n \lfloor \frac n T \rfloor \lfloor \frac m T \rfloor \sum _ {d | T} \sigma (d) [\sigma(d) \le a] \mu (\frac T d)
\end {aligned}
$$
如果没有后面 $a$ 的限制，那么可以发现后者是一个卷积的形式，$\sigma * \mu = id * 1 * \mu = id * \epsilon = id$ ，那么这个式子将十分优美，并且得到一个在线的 $O(q\sqrt n)$ 的算法。
但是不得不考虑 $a$ 的限制，记 $f(T) = \sum _ {d | T} \sigma (d) [\sigma(d) \le a] \mu (\frac T d)$ ，这是随着 $a$ 的增加而增加的函数，那么考虑将所有询问离线，将 $\sigma$ 和 $a$ 排序，每次询问前考察新增加的贡献，枚举倍数暴力加上。在数论分块中，我们需要快速地查询 $f$ 的前缀和，并且支持修改，考虑树状数组。
复杂度 $O(n \ln n \log n + q \sqrt n \log n)$ 。
查看代码
1 |
|