Luogu3327 [SDOI2015] 约数个数和

发表于 分类于 ， ， 阅读次数：

题意：给出 ，求

多组询问，。

此题的传统解法依赖于结论 ，借助二元积性函数的观点，可以有更自然的解法。

构造 ，，两者的贝尔级数为

令 ，则

可以看出 ，，其余位置为 ；即 ，其余位置为 。

于是

预处理 和 的前缀和后可以整除分块。复杂度 。