数论分块
定义：
数论分块可以在 \(O \sqrt{n}\) 的时间里计算一些有除法下取整的和式。
主要是 将 \(\frac{n}{d}\) 相同的数一起同时计算。
定理：
定理 \(1\):
\[a,b,c \in \mathbb{Z}, \lfloor \frac{a}{bc} \rfloor =\lfloor \frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor \]证明：
\[\frac{a}{b}=\lfloor \frac{a}{b} \rfloor+r \]带入将该值代入原式中即可。
定理 \(2\):
\[|\lfloor \frac{n}{d} \rfloor| \leq \lfloor 2\sqrt{n} \rfloor \]其中，\(n \leq d\) 且 \(n,d\) 为正整数 , \(|V|\) 表示集合 \(V\) 的元素个数。
证明：
对于 \(d \leq/\geq \lfloor \sqrt{n} \rfloor\) ，对应式子都只有 \(\lfloor \sqrt{n} \rfloor\) 种取值。
过程：
首先，为了好写博客，定义 \(| x |=\lfloor x \rfloor\) (小懒不算懒)
考虑含有 \(|\frac{n}{i}|\) 的求和式子。
对于任意一个 \(i \leq n\) 我们需要找到一个最大的 \(j\),使得 \(|\frac{n}{i}|=|\frac{n}{j}|\)
此时 \(j=|\frac{n}{|\frac{n}{i}|}|\)
显然 \(i\leq j\leq n\) .
我们设 \(k=|\frac{n}{i}|\) ,证明： 当 \(|\frac{n}{j}|=k\) 时， \(j\) 的最大值为 \(|\frac{n}{k}|\)
\[k \leq \frac{n}{j} < k+1 \]两边同时取倒数,再乘上 \(n\)，易得：
\[\frac{n}{k+1}<j \leq \frac{n}{k} \]因为 \(j \in \mathbb{Z}\) ，所以 \(j_{max}=|\frac{n}{k}|\)
利用上述结论，我们每次以 \([i,j]\) 为一块，分块求和即可。
例题：
题意：
计算 \(ans=\sum_{i=1}^n (k \mod i)\)
分析：
显然，这个式子可以转化成：
\[n \times k-\sum_{i=1}^n i \lfloor \frac{k}{i} \rfloor \]考虑后面的式子：
一开始 \(l=1\)
我们设 \(\lfloor \frac{k}{l} \rfloor=t\) ，分两种情况：
-
\(t \not ={0},r=min(\lfloor \frac{k}{t} \rfloor,n)\);
-
\(t= 0 ,r=n\).
然后如果没有到边界，直接 \(l=r+1\) ，再次计算 \(\lfloor \frac{k}{l} \rfloor\) 即可。
此时，这一段的答案就是：
\(\frac{(l+r)}{2}\)( 原式子中 \(i\) 的中间值) \(\times (r-l+1)\) (该区间长度) \(\times \lfloor \frac{k}{l} \rfloor\) (对应的值)
最后跳出循环，输出即可。
代码：
// 「luogu P2261」[CQOI2007]余数求和
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
int l,r,ans;
signed main(){
cin>>n>>k;
ans=k*n;
for(int l=1;l<=n;l=r+1){
int now=k/l;
if(now!=0) r=min(k/now,n);
else r=n;
ans-=(r-l+1)*(l+r)/2*(k/l);
}
cout<<ans<<endl;
system("pause");
return 0;
}