数论分块的模板，附带一些小证明

数论分块，一般是用来求类似的和式。

他为什么可以用分块做？因为一般只有最多个值。如何证明？

当时，因为只有种情况，所以值最多就只有种。

当时，因为值域范围就只能为（因为上一种情况已经把值的全取完了）。所以值也最多只有种。

因为值域最多就那么多种，所以就算是也轻轻松松。

那么怎么确定当值为某个数时，他的取的边界为多少？

也就是设，使这个分别是多少？

假设，则，所以。

则。

所以。

所以。（其实就是）

于是只要确定了这个值域区间的左端点（就是上个区间的右端点的），就能通过 n/(n/l) 来求得这个至于区间的。

然后这个区间的答案就是给做个前缀和，求个就可以了。

于是，板子题就来了。

ABC230E

就是上面的式子，只不过。这个求区间和就可以简化为。

核心代码：

ans=0;
cin>>n;
ll l=0, r=0;
while(r<n){
    l=r+1;
    r=n/(n/l);
    ans += ll(r-l+1) * (n/l);
}
cout<<ans<<'\n';

因为题目要求算，所以可以把它拆为。

现在考虑怎么求。

因为表示所有约数的和，所以一个数就可以对作出的贡献。

而因为那些可以接收产生的贡献的数一共有个。所以做出的贡献一共就有。

因为是分块整的，所以一次答案加上的就会有。这个等差数列只需要用求和公式处理一下就行了。

我似乎已经遗忘了小学数学了……

学过小学数学的都知道，一个数如果可以被质因数分解为，那么他的因数个数就是。如何证？

对于一个质因子，他可以选择把个拿出来贡献给因数。也可以选择不贡献。如果所有质因子都贡献出全部了那最后的因数就是这个数本身，如果所有质因子都不贡献那么最后的因数就是。所以一个质因子可以有种情况。一共个质因子，所以他的因数个数就是。

就转化成和上一道题很相似的形式了。只不过贡献不是因数本身，是。所以更好做了。