引理一
$$forall a,b,cinmathbb{Z},leftlfloorfrac{a}{bc} ight floor=leftlfloorfrac{leftlfloorfrac{a}{b} ight floor}{c} ight floor$$
略证：
egin{split} &frac{a}{b}=leftlfloorfrac{a}{b} ight floor+r(0leq r<1)\ Rightarrow &leftlfloorfrac{a}{bc} ight floor =leftlfloorfrac{a}{b}cdotfrac{1}{c} ight floor =leftlfloor frac{1}{c}left(leftlfloorfrac{a}{b} ight floor+r ight) ight floor =leftlfloor frac{leftlfloorfrac{a}{b} ight floor}{c} +frac{r}{c} ight floor =leftlfloor frac{leftlfloorfrac{a}{b} ight floor}{c} ight floor\ &&square end{split}
引理二
$$forall n in N, left|left{ lfloor frac{n}{d} floor mid d in N ight} ight| leq lfloor 2sqrt{n} floor$$
$|V|$表示集合$V$的元素个数
略证：
对于$d leq left lfloor sqrt{n} ight floor$，$left lfloor frac{n}{d} ight floor$有$left lfloor sqrt{n} ight floor$种取值.
对于$d geq left lfloor sqrt{n} ight floor$，有$left lfloor frac{n}{d} ight floor leq left lfloor sqrt{n} ight floor$，也只有$left lfloor sqrt{n} ight floor$种取值.
数论分块
数论分块的过程大概如下：考虑含有$left lfloor frac{n}{i} ight floor$的求和式子（$n$为常数）
对于任意一个$i$($i leq n$)，我们需要找到一个最大的$j$($i leq j leq n$)，使得$left lfloor frac{n}{i} ight floor = left lfloor frac{n}{i} ight floor$.
那么$j = left lfloor frac{n}{left lfloor frac{n}{i} ight floor} ight floor$.
略证：
egin{split} &leftlfloorfrac{n}{i} ight floor leq frac{n}{i}\ Rightarrow &leftlfloorfrac{n}{ leftlfloorfrac{n}{i} ight floor } ight floor geq leftlfloorfrac{n}{ frac{n}{i} } ight floor = leftlfloor i ight floor=i \ Rightarrow &ileq leftlfloorfrac{n}{ leftlfloorfrac{n}{i} ight floor } ight floor\ &&square end{split}
即$j = left lfloor frac{n}{left lfloor frac{n}{i} ight floor} ight floor$.
利用上述结论，我们每次以$[i,j]$为一块，分块求和即可.
实现
快速计算$sum left lfloor frac{n}{i} ight floor$的方法：
1 for(int l = 1, r; l <= n;l = r+1) 2 { 3 r = n / (n / l); 4 ans += (r-l+1) * (n / l); 5 printf("%d %d %d %d ", l, r, n/l, n/r); 6 }