前置知识

• 对于\(N^*=\{\lfloor n/i \rfloor|i\in[1,n]\}\).
  (1) 满足 \(\lfloor n/i \rfloor,x\in N^*\) 的最大的 \(i\) 为 \(\lfloor n/x \rfloor\).

(1)证明:
显然有 \(x\le n/i < x+1\)

\(\Leftrightarrow ix \le n < i(x+1)\)

\(\Leftrightarrow n/(x+1) < i \le n/x\)

又由于 \(i\in Z\) ,所以 \(\lfloor n/(x+1) \rfloor +1 \le i \le \lfloor n/x \rfloor\)
Q.E.D.

稍微变一下就是 \(\lfloor n/\lfloor n/i \rfloor \rfloor\)

而且我们证明最后得到的结论也很好用:

\[\lfloor n/(x+1) \rfloor +1 \le i \le \lfloor n/x \rfloor \]

然后给出一个关于向下取整的性质：

• \(\lfloor n/ab \rfloor=\lfloor \lfloor n/a \rfloor/b \rfloor\)

证明：
令 \(a/b=\lfloor n/a \rfloor +s\ (0 \le s < 1)\)
那么 \(\lfloor n/ab \rfloor=\lfloor 1/b(\lfloor n/a \rfloor+s) \rfloor =\lfloor \lfloor n/a \rfloor b \rfloor\)

对此我们可以计算 \(\sum_{i=1}^{n}\lfloor n/i \rfloor\)

OI wiki上的图明了的解释了这一切

发现函数值是连续一段一段的，直接有了写方的代码。

ll l=1,r=0,ans=0;
while(l<=n){
	r=n/(n/l);
	ans=ans+(r-l+1)*(n/l);
	l=r+1;
}
printf("%d\n",ans);

整数分块

用来计算形如 \(\sum_{i=1}^{n}f(i)g(\lfloor \frac{n}{i} \rfloor)\) 的和式。

实际上是上面的那个东西的推广。

其实没多大差别，我们只需要能够求出一段的连续区间的权值和即可，这个我们用前缀和即可。

ex:

ll l=1,r=0,ans=0;
while(l<=n){
	r=n/(n/l);
	ans=ans+(sum[r]-sum[l-1])*(n/l);
	l=r+1;
}
printf("%d\n",ans);

没了，结束。