【BZOJ3529】【SDOI2014】数表

OrzXPZ

首先显然\((i,j)位置的值为\sigma((i,j))\)

那么答案就是

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\sigma((i,j))[\sigma((i,j))\le a]$$

这个约束条件不好处理。。那么先不管他

假设没有约束条件,令

$$f(x)=\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=x]$$

答案就是

$$\sum_{i=1}^{n}\sigma(i)f(i)$$

把\(f(x)\)变化一下

$$f(x)=\sum_{d=1}^{\lfloor\frac{n}{x}\rfloor}\mu(d)\lfloor\frac{n}{xd}\rfloor\lfloor\frac{m}{xd}\rfloor$$

代回去

$$ans=\sum_{i=1}^{n}\sigma(i)\sum_{d=1}^{\lfloor\frac{n}{i}\rfloor}\mu(d)\lfloor\frac{n}{id}\rfloor\lfloor\frac{m}{id}\rfloor$$

枚举\(id\)为\(i\)

$$ans=\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor\sum_{d|i}\mu(\frac{i}{d})\sigma(d)$$

现在考虑\(a\)的限制,那么就是后面部分只有不大于\(a\)的\(\sigma(d)\)才能计入答案。

将询问按照\(a\)排序,每次加入不大于\(a\)的\(\sigma(d)\),用树状数组维护后面部分的前缀和。

于是加入的复杂度\(O(\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor logn=O(nlog^2n)\)

询问的复杂度\(O(Q\sqrt{n}logn)\)

说点什么

您将是第一位评论人!

提醒
wpDiscuz