數(shù)論分塊

如何在\(O(\sqrt{n})\)復(fù)雜度內(nèi)計算 \(\sum \limits_{i= 1}^n \lfloor \frac{n}{i} \rfloor\) ?

一個直觀的想法是， \(\lfloor \frac{i}{n} \rfloor\) 必然存在一個相等的段，我們以\(n = 15\) 為例：

我們可以看到該段區(qū)間內(nèi)當(dāng) \(n\) 取值為 \([6, 8], [9, 15]\)內(nèi)的值都是相等的值，我們考慮如何以每個這樣的塊為單位來計算要求的值。

考慮左端點為 \(l\), 我們設(shè)右端點為 \(r\), 有如下等式

例題

CQOI2007-余數(shù)求和

#include <iostream>

using i64 = long long;

int main() {
	i64 n, k; std::cin >> n >> k;

	i64 sum = 0;

	i64 l = 1, r = 0;

	while (l <= k && l <= n) {
		r = std::min(k / (k / l), n);

		i64 t = r - l + 1;

		sum += t * k - (l + r) * t / 2 * (k / l);

		l = r + 1;	
	}	

	std::cout << sum + std::max(0LL, 1LL * (n - k) * k);
}