Trick-整除分块（数论分块）

整除分块：
对于类似于\(solve_{d=1}^{n}(\frac{n}{d})\)的式子, \(\frac{n}{d}\)的值的个数不超过\(\sqrt n\)个（下面有证明），故可以对于每一个结果去计算其贡献。
代码如下:

void calc(int n) {
   for(int l = 1, r; l <= n; l = r + 1) {
       r = n / (n / l);//d在区间[l,r]的n/d大小相同
       ans += n / d * solve(l, r);
   }
}

证明：
记\(\frac{n}{d}\)为x。x的取值范围在[1,n]。显然，[1,\(\sqrt n\)]的x更密集，(\(\sqrt n\), n]的x更稀疏。
因为d从1到n，只有d在[1,\(\sqrt n\)]时，\(\frac{n}{d}\)在(\(\sqrt n\), n]，所以\(\frac{n}{d}\)在(\(\sqrt n\), n]的个数不超过\(\sqrt n\)
\(\frac{n}{d}\)从1到\(\sqrt n\)一共\(\sqrt n\)个数，所以总个数为\(O(\sqrt n)\)的。

一般式子中出现下取整，直接无脑整除分块。