数论分块

前置知识

• 对于$N^={\lfloor n/i \rfloor\mid 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);

没了，结束。