约数个数和

题面

其中表示的约数个数。

题解

Lemma

证明：考虑质因数的影响。若，。则对等式左边的贡献是倍，即。因为我们考虑所有的约束可以分别乘上，约数总数量变为原来的倍。 对于等式右边，假设对于有一个合法的约数对，那么在中可以新添一些合法的约数对：

新添了倍个数对，也就是成为了原先的倍。可以发现等式左右两边都变为原来的倍，沿着这个思路可以归纳证明该等式成立。

因此，该式子可以转化为：

然后我们转而枚举：

其中，因此可得：

莫比乌斯反演

上面推倒中 为莫比乌斯反演，推倒过程如下：
设

那么

根据二项式定理，易知该式子的值在 即 时值为 否则为 , 也就证明了莫比乌斯反演。

在最外层枚举：

枚举改为枚举的倍数，假设：

我们设，则可得到

注意到对于，只有种取值，所以我们可以预先用的复杂度将所有的预处理出来。最后用的时间完成对的预处理和最终的求和，最后的复杂度为。

分块除法

对于的具体计算方法，我们可以用分块除法。对于一个数，我们可以将它分成个块，然后对于每个块，我们可以用的时间计算出这个块的和。这样我们就可以用的时间计算出的值。具体代码如下:

for(int j = 1; j <= n; ++j){
    int val = n / j, next = n / val; 
    f[n] += (next - j + 1) * val;
    j = next;
}