专栏文章

数论分块

SSnowFlavour
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip249kj
此快照首次捕获于
2025/12/03 04:55
3 个月前
此快照最后确认于
2025/12/03 04:55
3 个月前
查看原文

一类问题

有一类问题，要求你求：
∑i=1n⌊ni⌋\sum_{i=1}^n\lfloor \frac{n}{i} \rfloor
这样的东西。nn 的范围往往很大（109∼101510^9 \sim 10^{15}），要用低于线性的复杂度。

思路

一般而言，这种东西的性质就是：虽然 nn 很大，但是很多的数都是相同的：
ii12345678910
⌊10i⌋\lfloor \frac{10}{i} \rfloor10532211111
所以我们没必要把每个 ⌊ni⌋\lfloor \frac{n}{i} \rfloor 都求出来。
考虑会有多少种可能的 ⌊ni⌋\lfloor \frac{n}{i} \rfloor 的取值：
在 n\sqrt{n} 以后，f(x)=nxf(x)=\frac{n}{x} 的导数小于 11，因此 f(x)f(x) 的变化速度要低于 xx，因此 ∀y∈[1,n]∩N\forall y \in [1,\sqrt n] \cap \mathbb{N} 都是可能的取值。
在 n\sqrt{n} 以前，一共只有 n\sqrt n 种可能的取值，而由于导数大于 11，∀x∈[1,n]∩N\forall x \in [1,\sqrt n] \cap \mathbb{N} 所对应的 f(x)f(x) 都不同。
因此，变化次数为 O(n)O(\sqrt n)。
那么，怎么求出每种取值的区间呢？
假设一种取值对应的区间为 [l,r][l, r]，则：
⌊nl⌋≤nr<⌊nl⌋+1\lfloor \frac{n}{l} \rfloor \le \frac{n}{r} < \lfloor \frac{n}{l} \rfloor+1
所以：
r⩽⌊n⌊nl⌋⌋r\leqslant\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{l}\right\rfloor}\right\rfloor
rmax=⌊n⌊nl⌋⌋r_{max}=\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{l}\right\rfloor}\right\rfloor
THE \sqrt{} END
（又补完一篇博客）

Code

CPP
#include <iostream>
using namespace std;
using ll = long long;
int main() {
	ll n, k;
	cin >> n >> k;
	ll l, r;
	ll ans = n * k;
	for (l = 1; l <= n; l = r + 1) {
		if (k / l) r = min(k / (k / l), n);
		else r = n;
		ans -= (r - l + 1) * (k / l) * (l + r) / 2;
	}
	cout << ans << endl;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...