数论分块
数论分块
也叫整除分块
是用于快速处理类似于
\[\sum_{i=1}^n \lceil \frac{n}{i} \rceil \text{或者} \sum_{i=1}^n \lfloor \frac{n}{i} \rfloor \]式子的一种方法
复杂度：\(O(\sqrt{n})\)
思想阐述：以向下取整为例
对于\(\lfloor \frac{n}{i}\rfloor\)，来说，它的值是呈块状递减分布的，至多有\(2\sqrt{n}\)个块
这些块的分布规律是：
对于一个块内的一个点\(l\)，我们可以得到块的右端点为\(\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor\)
写成代码就是
int get(int l){return n/(n/l);}
非常的\(so\) \(easy\)
那么我们要求的 \(\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor\)
也就迎刃而解了
for(int i=1;i<=n;i++){
int r=get(i);
ans+=(n/i)*(r-i+1);
i=r;
}
还有一个性质：
\[\text{对于}a,b,c\in\mathbb{Z}\text{,有}\lfloor\frac{a}{bc}\rfloor=\left\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\right\rfloor \]来一道例题吧：
题意简述：给定\(n,k\)求：
\[\sum_{i=1}^n (k\bmod i) \]注意到\(k \bmod i=k-\lfloor \frac{k}{i} \rfloor \times i\)
所以
\[\sum_{i=1}^n (k\bmod i) = \sum_{i=1}^n \left(k-\lfloor \frac{k}{i} \rfloor \times i\right) = \sum_{i=1}^n k-\sum_{i=1}^n \lfloor \frac{k}{i} \rfloor \times i=n\times k -\sum_{i=1}^n \lfloor \frac{k}{i} \rfloor \times i \]由于数论分块，我们设\(\sum_{i=1}^n \lfloor \frac{k}{i} \rfloor\)分成了\(m\)个块，各个块的左右端点记作\(L_i,R_i(i\in [1,m])\)
则原式子可化为：
\[\sum_{i=1}^m \sum_{j=L_i}^{R_i} (\lfloor \frac{k}{L_i} \rfloor \times j)=\sum_{i=1}^m\left(\lfloor \frac{k}{L_i} \rfloor \times \sum _ {j=L_i}^{R_i} j\right) = \sum_{i=1}^m\left(\lfloor \frac{k}{L_i} \rfloor \times \frac{(L_i+R_i)(R_i-L_i+1)}{2} \right) \]综上所述，答案即为：
\[n\times k - \sum_{i=1}^m\left(\lfloor \frac{k}{L_i} \rfloor \times \frac{(L_i+R_i)(R_i-L_i+1)}{2} \right) \]\(Code:\)
cin>>n>>k;
ans=n*k;
for(int x=1,gx;x<=n;x=gx+1){
gx=k/x?min(k/(k/x),n):n;
ans-=(k/x)*(x+gx)*(gx-x+1)/2;
}
cout<<ans;