数论分块

整理日期按学习顺序编排，不代表原始发表时间。实际整理于 2026-10-23。

难度为阅读建议，可从 ACM 学习索引 按阶段阅读。

将O（n)优化成o（根号n）

[CQOI2007] 余数求和

题目描述

给出正整数 $n$ 和 $k$，请计算

$$G(n, k) = \sum_{i = 1}^n k \bmod i$$

• 对于 $100\%$ 的数据，保证 $1 \leq n, k \leq 10^9$

void solve(){
	int n,k;cin>>n>>k;
	int ans=n*k;
	//注意推导公式字母不要弄混
	for(int l=1,r=1;l<=n;l=r+1){
		if((k/l)==0)break;//注意特判分母为0的情况，不然会RE
		r=k/(k/l);
		r=min(n,r);//防止多算
		//cerr<<l<<" "<<r<<endl;
		ans-=(k/l)*(r-l+1)*(l+r)/2;
	}
	cout<<ans<<endl;
	
}