余数求和——除法分块

传送门：余数求和

本题目中需要计算 \(\sum_{i=1}^{n}{k \mod\ i}\)

对于 k mod i , 在写高精度取模时，曾表示为：\({k}-{i}\times\lfloor \frac{k}{i} \rfloor\)

故本题中，可以继续采用这种计算方式，将其拆分为：\(ans=\sum_{i=1}^{n}{k}-{i}\times{\lfloor \frac{k}{i} \rfloor}\)

进而，有：\(ans={n}\times{k}-\sum_{i=1}^{n}{i}\times{\lfloor\frac{k}{i}\rfloor}\)

于是,对于\(\lfloor \frac{k}{i} \rfloor\)可以用分块进行处理，取值约为：\(\sqrt{k}\)种，故复杂度约为O(\(\sqrt{k}\))

#include<iostream>
#include<cstdio>
#include<cstring>
#include<math.h>
#include<algorithm>
#define ll long long
using namespace std;

ll n,k;
ll ans;

int main(void)
{
	scanf("%lld%lld",&n,&k);
	
	ans=n*k;
	
	for(int l=1,r;l<=n;l=r+1)
	{
		if(k/l!=0) r=min(k/(k/l),n);
		else r=n;
		ans-=(k/l)*(r-l+1)*(l+r)/2;//当前块的t*当前块元素的个数*当前块中元素的平均值 
	}
	
	printf("%lld",ans);
	
	return 0;
}

余数求和——除法分块

原文：https://www.cnblogs.com/jd1412/p/13282403.html