Problem:

求[tex]\sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C d(ijk)[/tex]。对2^30取模。

Lemma:

令[tex]S_d(r,k)=\sum_{i=1}^r d(ki)[/tex]

令[tex]k=p^\alpha q[/tex], 其中[tex](p,q)=1[/tex]

则有[tex]S_d(r,k)=(\alpha+1)S_d(r,q)-\alpha S_d([\frac{r}{p}],q)[/tex]

这个公式可以由打个小表轻松得出。

Solution:

可以把所求的值整理成[tex]S_d(r,k)[/tex]的形式。

即 [tex]\sum_{i=1}^A \sum_{j=1}^B S_d(C,ij)[/tex]

注意到需要计算的所有的[tex]S_d(r,k)[/tex]中,

k的取值种数是[tex]N^2[/tex]的,

r的取值是所有[tex]\left \lfloor \frac{C}{i}\right\rfloor[/tex], 于是是[tex]\sqrt{N}[/tex]的。

于是可以使用记忆化，在[tex]N^\tfrac{5}{2}[/tex]的时间内解决这个问题。

空间方面，动态申请内存, 从大到小枚举[tex]ij[/tex], 并在计算完后释放[tex]ij[/tex]的空间即可。

这种算法的缺点在于代码量较大,

优点是所利用的公式简单, 可以打表+目测得到,

思维难度低, 适合我这种无脑的中老年人选用。

而且做法比较固定,需要计算[tex]S_f(r,k)=\sum_{i=1}^r f(ki)[/tex]的问题都可以这么解决。

PS

最后, 大战了Tex觉得浑身舒爽, 233.

• 相关文章
• 全局相关文章