P3636曲面

[洛谷](https://www.luogu.com.cn/problem/P3636

做数学题一定要列式子！！

[ans=sum_isum_jsum_k(i+j+k)^2=sum_isum_jsum_k(i^2)+(2i(j+k))+(j^2+k^2+2jk),ijk<=n ]

于是整除分块套整除分块

时间复杂度(O(n))

#include<bits/stdc++.h>
using namespace std;
#define re register
#define LL long long
const int mod=10007;
inline int s1(int n){
	return (LL)n*(n+1)/2%mod;
}
inline int s2(int n){
	n%=mod;
	return (LL)n*(n+1)/2*(n*2+1)/3%mod;
}
inline int solve(int n){
	int ans=0;
	for(re int l=1,r,xx,yy,res1,res2,res3;l<=n;l=r+1){
		r=n/(n/l);
		res1=res2=res3=0;
		for(re int ll=1,rr,nn=n/l;ll<=nn;ll=rr+1){
			rr=nn/(nn/ll);
			res1=((LL)(rr-ll+1)*(nn/ll)+res1)%mod;
			xx=s1(rr)-s1(ll-1);
			yy=s1(nn/ll);
			res2=((LL)xx*(nn/ll)+(LL)(rr-ll+1)*yy+res2)%mod;
			res3=((LL)xx*yy*2+res3)%mod;
			xx=s2(rr)-s2(ll-1);
			yy=s2(nn/ll);
			res3=((LL)xx*(nn/ll)+(LL)(rr-ll+1)*yy+res3)%mod;
		}
		ans=((LL)(r-l+1)*res3+(LL)res2*(s1(r)-s1(l-1))*2+(LL)(s2(r)-s2(l-1))*res1+ans)%mod;
	}
	return (ans+mod)%mod;
}
int main(){
	int a,b;cin>>a>>b;
	cout<<(solve(b)-solve(a-1)+mod)*4%mod;
	return (0-0);
}