数论分块

数论分块

在P2424偶然学到了这个算法，觉得很有意思，于是单拎出来再学习一下。

数论分块，又叫整数分块，解决 $f(n) = \sum_{i=1}^{n}g(i) \times \lfloor \frac{n}{i} \rfloor$ 一类问题。观察发现 是成段出现，比如说 时数列是这样的：

设区间的右端点为 ，$r = \frac{n}{\lfloor \frac{n}{l} \rfloor} $ ，。

证明如下：

，所以 ，因此

有了左右端点后，就可以 求块内的答案，总复杂度

总结一下，数论分块用于在较优时间复杂度内计算可分为一些块的式子，通过将贡献相同的下标合为一块一起计算块内答案，从而起到优化时间复杂度的作用。

还有一些常用的公式：

题目

P3935 Calculating

不难发现 的值就是 的约数个数，然后就是板子。

// 
// #include<bits/stdc++.h>
// #define int long long
// using namespace std;
// void solve(){
// 	int ans = 0;
// 	int n;
// 	scanf("%lld", &n);
// 	int r = 1;
// 	for(register int l = 1; l <= n; l = r + 1){
// 		r = n / (n / l);
// 		ans += (r - l + 1) * (n / l);
// 	}
// 	printf("%lld\n", ans);
// 	return;
// }
// signed main(){
// 	int T;
// 	cin >> T;
// 	while(T --){
// 		solve();
// 	}
// }
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+7;
const int mod = 998244353;
int solve(int n){
	if(n<=1) return n;
	int ans=0;
	int r;
	for(int l=1;l<=n;l=r+1){
		r=n/(n/l);
		ans+=(n/l)*(r-l+1);
	}
	return ans;
}
int query(int n){
	int r;
	int ans = 0;
	for(int l = 1; l <= n; l = r + 1){
		r = n / (n / l);
		ans += (n / l) * (r - l + 1);
		ans %= mod;
	}
	return ans % mod;
}
signed main(){
	int l, r;
	cin >> l >> r;
	cout << (query(r) - query(l - 1) + mod) % mod;
}

P2261 [CQOI2007] 余数求和

式子可以转换成 ，然后就是板子。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+7;
int query(int n, int k){
	int r;
	int ans = 0;
	for(int l = 1; l <= n; l = r + 1){
		if(k / l == 0) r = n;
		else r = k / (k / l);
	if(r &gt; n) r = n;
	ans += (k / l) * (r - l + 1) * (l + r) / 2;
}
return n * k - ans;

}

signed main(){

int n, k;

cin >> n >> k;

cout << query(n, k);

}

还有些题 鸽到csp之后吧