自动搬运

查看原文

来自洛谷，原作者为

	lemondinosaur 那跑过去的昼夜是孤独的修炼

搬运于2025-08-24 21:51:02，当前版本为作者最后更新于2021-09-17 19:11:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目传送门

---

首先将 $\sum_{i=a}^b C(i)$ 转换成 $\sum_{i=1}^b C(i)-\sum_{i=1}^{a-1} C(i)$，

那么题目就转换成求 $\sum_{1\leq xyz\leq n} (|x|+|y|+|z|)^2$。

三个数相乘是正数当且仅当两负一正或者全是正数，一共四种情况。

再将平方拆开可以化简成

$$4 \sum_{xyz\leq n} x^2+y^2+z^2+2(xy+xz+yz)$$

考虑三个平方项是等价的，$xy,xz,yz$ 也是等价的，所以就是

$$(12 \sum_{xyz\leq n} x^2)+(24 \sum_{xyz\leq n} xy) $$

对于左边这一部分考虑枚举 $x$，就可以转换成 $\sum_{x=1}^n x^2f(\lfloor\frac{n}{x}\rfloor)$。

其中 $f(n)=\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor$，这两个式子都可以整除分块实现。

对于右边这一部分考虑枚举 $z$，就可以转换成 $\sum_{z=1}^n g(\lfloor\frac{n}{z}\rfloor)$。

$$g(n)=\sum_{i=1}^n i\frac{(\lfloor\frac{n}{i}\rfloor+1)\times (\lfloor\frac{n}{i}\rfloor)}{2} $$

同样也可以用整除分块实现。

---

代码

#include <cstdio>
using namespace std;
const int mod=10007;
const int i4=(mod+1)>>2;
const int i6=(mod+1)/6;
int l,r;
int mo(int x,int y){return x<y?x-y+mod:x-y;}
void Mo(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
int sf(int n){
	int _n=n%mod;
    return 1ll*i6*_n*(_n+1)*(_n<<1|1)%mod;
}
//1^2+2^2+...+n^2=n*(n+1)*(2n+1)/6

int query0(int n){//f(n)
	int ans=0;
	for (int l=1,r;l<=n;l=r+1)
		r=n/(n/l),Mo(ans,(r-l+1ll)*(n/l)%mod);
	return ans;
}
int query1(int n){//g(n)
	int ans=0;
	for (int l=1,r;l<=n;l=r+1)
	    r=n/(n/l),Mo(ans,i4*(1ll*(l+r)%mod*(r-l+1)%mod)*(1ll*(n/l)*(n/l+1)%mod)%mod);
	return ans;
}
int query(int n){
	int ans=0;
	for (int l=1,r;l<=n;l=r+1){
		r=n/(n/l),Mo(ans,12*mo(sf(r),sf(l-1))%mod*query0(n/l)%mod);//左边这一部分 
		Mo(ans,24*(r-l+1ll)%mod*query1(n/l)%mod);//右边这一部分
	}
	return ans;
}
int main(){
	scanf("%d%d",&l,&r);
	printf("%d",mo(query(r),query(l-1)));
	return 0;
}