【BZOJ3994】【SDOI2015】约数个数和

$$\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)$$

每个\(ij\)的约数都可以表示为\(\frac{pj}{q}\),其中\(p|i\)且\(q|j\)并且\((p,q)=1\)

那么就是求

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{p|i}\sum_{q|j}[(p,q)=1]$$

$$\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=1]\left\lfloor\frac{n}{i}\right\rfloor\left\lfloor\frac{m}{j}\right\rfloor$$

莫比乌斯反演

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|i,d|j}\mu(d)\left\lfloor\frac{n}{i}\right\rfloor\left\lfloor\frac{m}{j}\right\rfloor$$

$$\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\left\lfloor\frac{n}{id}\right\rfloor\left\lfloor\frac{m}{jd}\right\rfloor$$

令\(g(n)=\sum_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor\)

$$\sum_{d=1}^{n}\mu(d)g(\left\lfloor\frac{n}{d}\right\rfloor)g(\left\lfloor\frac{m}{d}\right\rfloor)$$

发现实际上\(g(n)=\sum_{i=1}^{n}d(i)\),那么我们可以预处理出来\(g\)

然后根号直接搞就可以了

说点什么

1 评论 在 "【BZOJ3994】【SDOI2015】约数个数和"

提醒
排序:   最新 | 最旧 | 得票最多
成员

第一个%

wpDiscuz