P2261 CQOI2007-余数求和


前置知识

![[除法分块]]

题目分析

学过分块除法的同学就很敏感了,$\sum^n_{i=1}{i*\lfloor \frac{k}{i}\rfloor}$ 特别适合用除法分块处理,没学过的先学习一下分块除法。

到此本题大体思路基本完成,下面对一些细节进行补充(看代码部分的备注)。

代码

#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
	ll n,k,Ans=0,l=1,r;
	cin>>n>>k;
	while(l<=n)
	{
		if(l>k) break;//l>k时,k/l=0,没有必要继续计算,并且继续计算会出现 k/0 的错误
		r=k/(k/l);//当前的区间就是l~r,这个区间的值均为 n/l
		if(r>n) r=n;// 我们计算的是 k 对于的分块区间,可能出现r>n  的情况 
		Ans = Ans + (k/l)*(r-l+1)*(l+r)/2;//区间中每个数均为 
		l=r+1;
	}
	Ans=(n*k-Ans);//公式
	cout<<Ans;
	return 0;
}

如果本文帮助到了你,帮我点个广告可以咩(o′┏▽┓`o)


文章作者: Anubis
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Anubis !
评论
  目录