BZOJ1257 余数之和

题目大意：

给出正整数$n$和$k$ 计算$j(n, k)=k \mod 1 + k \mod 2 + k \mod 3 + … + k \mod n$的值

题解：

首先$k\mod n=k-\lfloor{\frac{k}{n}}\rfloor\cdot n$

那么$j(n,k)$即为$n\cdot k-\sum_{i=1}^{n} \lfloor{\frac{k}{i}}\rfloor \cdot i$

所以重点是求$\sum_{i=1}^{n} \lfloor{\frac{k}{i}}\rfloor \cdot i$

如果直接暴力肯定会超时 但是我们注意到$\lfloor{k/i}\rfloor$最多只有$2\sqrt{k}$个取值（有求约数的过程可知） 所以我们可以对$\lfloor{k/i}\rfloor$的值进行分块

数论分块

我们先来介绍一种叫数论分块的东西 对于任一个$i$我们要找到一个$j$满足$\lfloor{\frac{n}{i}}\rfloor=\lfloor{\frac{n}{j}}\rfloor$且$j$最大 结论为$j=\Big\lfloor\frac{n}{\lfloor{\frac{n}{i}}\rfloor}\Big\rfloor$

略证:

$\Big\lfloor\frac{n}{\lfloor{\frac{n}{i}}\rfloor}\Big\rfloor\ge\Big\lfloor\frac{n}{\frac{n}{i}}\Big\rfloor=\lfloor i\rfloor=i$

所以我们可以把$[i,j]$看作一个整体 这样对于一块 它就是一个等差数列求和

设$w=\lfloor{\frac{k}{i}}\rfloor,l=i,r=\lfloor{\frac{k}{w}}\rfloor$

那么该段所求即为$w\cdot(r-l+1)\cdot(r+1)/2$

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
ll n,k;
ll ans;
int main()
{
	cin>>n>>k;
	ans=n*k;
	if(n>k) n=k;
	ll l,r;
	for(ll i=1;i<=n;i=r+1)
	{
		ll w=k/i;
		r=k/w,l=i;
		if(r>n) r=n;
		ans-=w*(l+r)*(r-l+1)/2;
	}
	cout<<ans<<endl;
	return 0;
}