【数论】数论分块

2024-18-19 ·最后更新时间：2024-18-19

\(\Large\mathcal{1,solution(1)}\)
如果我们把数 \(n\) 与小于等于 \(n\) 的数 \(i\) 的对应关系打印在表格上会是这样。

可以发现 \(\Large\lfloor\frac{n}{i}\rfloor\) 的数是有重复的，那么我们可不可以根据重复的特点来计算 \(\Large\lfloor\frac{n}{i}\rfloor\) 的数值呢？答案是可以的，这也就是数论分块的主要思想。

\(\Large\mathcal{2,verification}\)
为了保证算法的正确性我们要对其进行时间复杂度分析。

1. 当 \(i>\sqrt{n}\) 时，那么此时 \(\Large\lfloor\frac{n}{i}\rfloor\) 最多有 \(\sqrt{n}\) 种取值。
2. 当 \(i\leq\sqrt{n}\) 时，那么此时 \(\Large\lfloor\frac{n}{i}\rfloor\) 也最多有 \(\sqrt{n}\) 种取值。

所以最终我们可以得到时间复杂度为 \(O(\sqrt{n})\)

\(\Large\mathcal{3,solution(2)}\)
接下来我们将要对边界进行分析，判断什么时候当前在哪一个块中。

首先我们假设当前块的左端点是 \(l\) ，那么根据我们之前的分析 \(\lfloor\frac{n}{l}\rfloor\) 就一定是我们当前块的数值，那么右端点该怎么求，对右端点 \(r\) 进行分析，其本质上就是满足 \(\lfloor\frac{n}{l}\rfloor=\lfloor\frac{n}{r}\rfloor\) 的 \(r\) 的最大值，等等，那不就是说明了 \(r={\Large\lfloor}\frac{n}{\lfloor\frac{n}{l}\rfloor}\Large\rfloor\) 吗！？

那么这样我们就顺利的得到了 \(r\) 的值并且可以求出当前块的所有数的和，也就是 \(S=(r-l+1)×\lfloor\frac{n}{l}\rfloor\)

\(\Large\mathcal{4,code}\)

int division_block(int n){
    int ans=0;
    for(int l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        ans+=n/l*(r - l + 1);
    }
    return ans;
}

\(\Large\mathcal{5,example}\)
题目连接：[CQOI2007] 余数求和
思路：因为 \(a \mod b\) 可以转换为 \(a-\lfloor\frac{a}{b}\rfloor b\) 所以原式也就转化成了 \({\Large\sum_{i=1}^n} k-\lfloor\frac{k}{i}\rfloor i\) 可以发现 \(k\) 不会随着 \(i\) 的变化而变化，所以可以将 \(k\) 放在西格玛外面，\(nk-{\Large\sum_{i=1}^n}\lfloor\frac{k}{i}\rfloor i\) 于是在这么多奇妙转化下，我们可以发现式子最后不就变成了数论分块的模板吗！？所以直接套模板就行，细节看代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,ans;
signed main(){
	cin>>n>>k;
	for(int l=1,r;l<=n;l=r+1){
		r=k/l==0?n:min(n,k/(k/l));
		ans+=(k/l)*(l+r)*(r-l+1)/2; 
	}
	cout<<n*k-ans<<endl；
	return 0;
}

\(\color{white}{代码有惊喜qwq}\)