P2261 CQOI2007-余数求和

前置知识

除法分块

题目分析

$$\begin{matrix} \sum^n_{i=1}{k\ mod\ i}&=\sum^n_{i=1}{(k-i*\lfloor \frac{k}{i}\rfloor)}\\ &=n*k-\sum^n_{i=1}{i*\lfloor \frac{k}{i}\rfloor} \end{matrix}$$

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

$$=n*k-\sum{\lfloor \frac{k}{l}\rfloor*\sum^r_{l}{i}}\\ =n*k-\sum{\frac{(l+r)*(r-l+1)}{2}*\lfloor \frac{k}{l}\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;
}