整数分块 - 算法 | PocketCat blog

整数分块可以以 log (n) 的时间复杂度内求出 ${\sum_{i=1}^n\lfloor n/i \rfloor}$

# 小 G 的约数

# 解法

单纯求 F (n) O (n) 求出，现在求 $\sum_{i=1}^nF_i$ ，可以换种思路，从个体对整体的贡献下手，对于每一个约数求有这个约数的所有数数量，显然是 n/i 个，然后乘上 i，那么问题就转化为了 ${\sum_{i=1}^n\lfloor n/i \rfloor*i}$ ，很明显的整数分块模板，什么是整数分块，考虑 n=10 的时候 n/i 的表

i: 1 2 3 4 5 6 7 8 9 10

n/i: 10 5 3 2 2 1 1 1 1 1

发现数字呈从大到小块状分布，只要知道了一个块的左端和右端就能直接算出这个块的 n/i 的和，这里有一个结论： $N/i==N/i'时，i'的最大值：N/(N/i)$ ,i' 也就是右端点，因此可以枚举每一段区间，n/i 的所有数字中不同数字的数量不会超过 2*sqrt (n) 个，因此时复就是 sqrt (n)

# 整数分块函数

	ll get(ll x){
	ll ret=0;
	for(ll i=1;i<=x;i++){
	ll r=x/(x/i);
	ret+=x/i*(r-i+1);
	i=r; // 把指针移到右端点的下一个位置，这里移到右端点是因为 i++
	}
	return ret;
	}

# ACCODE

	#include <bits/stdc++.h>
	#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
	#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
	using namespace std;
	typedef long long ll;
	typedef unsigned long long ull;
	const int MAXN=1e6+100;
	const double pi=acos(-1);
	const int MOD=1e9+7;
	const int INF=0x3f3f3f3f;
	const int SUB=-0x3f3f3f3f;
	const int eps=1e-4;
	ll get(ll x){
	ll ret=0;
	for(int i=1;i<=x;i++){
	ll r=x/(x/i);
	ret+=(r-i+1)(x/i)(i+r)/2; // 这里要乘以等差数组前缀和
	i=r;
	}
	return ret;
	}
	int main(){
	ios;
	ll n;
	cin>>n;
	cout<<get(get(n))<<'\n';
	return 0;
	}