数论分块

---

title: 数论分块
categories:

• ICPC
  tags:
• null
  abbrlink: 4a670895
  date: 2023-09-14 00:00:00

---

将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;
	
}