P2261 [CQOI2007]余数求和

原题传送门

题目大意：给出正整数$n$,$k$,请计算$G(n,k)=\sum_{i=1}^n\ k\ mod\ i$
思路：一道整除分块的入门题

整除分块的基本形式为：$\sum_{i=1}^n\lfloor \frac{n}{i}\rfloor$
对于任意一个$i(i\le n)$,我们要找到一个最大的$j(i\le j\le n)$，使得$\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{j}\rfloor$,那么此时$j=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$

显然$i\le j\le n$(证明从略)，设$k=\lfloor\frac{n}{i}\rfloor$，当$\lfloor\frac{n}{j}\rfloor=k$，$j_{max}=\lfloor\frac{n}{k}\rfloor$(证明从略)

那么对于每次以$[i,j]$为一块，分块求和即可

Code:

for(ll l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        ans+=(r-l+1)*(n/l);
}

对于本题来说，$\sum_{i=1}^n\ k\ mod\ i=\sum_{i=1}^n\ k-i*\lfloor\frac{k}{i}\rfloor=n*k-\sum_{i=1}^n\ i*\lfloor\frac{k}{i}\rfloor$

对于$\sum_{i=1}^n\ i*\lfloor\frac{k}{i}\rfloor$，我们把每块$[l,r]$对应的$\sum_{i=l}^r\ i*\lfloor\frac{k}{i}\rfloor$中，令$T=\sum_{i=l}^r\lfloor\frac{k}{i}\rfloor$，$\sum_{i=l}^r\ i*\lfloor\frac{k}{i}\rfloor=T*\sum_{i=l}^r\ i=T*\frac{l+r}{2}$

复杂度$O(\sqrt n)$

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+10,mod=1e9+7;
typedef long long ll;
ll n,k;
int main(){
	cin>>n>>k;
	ll ans=n*k;
	for(ll l=1,r;l<=n;l=r+1){
		if(k/l!=0) r=min(n,k/(k/l));
		else r=n;
		ans-=(l+r)*(k/l)*(r-l+1)/2;
	}
	cout<<ans<<endl;
	return 0;
}