数论分块

参考资料

• 数论分块 - OI Wiki

实现

for(ll l=1,r;l<=n;l=r+1)
{
	r=n/(n/l);
	ans+=(r-l+1)*(n/l);
}

例题

洛谷 UVA11526 H(n)

给定 $T$ 次询问，每次询问一个正整数 $n$，求 $\sum_{i=1}^{n} \left\lfloor\frac{n}{i}\right\rfloor$。

Code (1)

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		ll ans=0;
		for(ll l=1,r;l<=n;l=r+1)
		{
			r=n/(n/l);
			ans+=(r-l+1)*(n/l);
		}
		cout<<ans<<'\n';
	}
	return 0;
}