先转化问题：

然后考虑计算 的 的个数，并记作 ，这样所求即为：

考虑快速计算 ：

对 和外层和式均整除分块即可，复杂度不高于 。