脚本宝典收集整理的这篇文章主要介绍了#整除分块#洛谷 3636 曲面，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目传送门

分析

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

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

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

再将平方拆开可以化简成

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

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

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

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

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

代码

#include <cstdio>
#define rr register
using namespace std;
const int mod=10007;
inline signed mo(int x,int y){return x<y?x-y+mod:x-y;}
inline void Mo(int &amp;x,int y){x=x+y>=mod?x+y-mod:x+y;}
inline signed sf(int n){return 3336*(1ll*n*(n+1)%mod)*(n<<1|1)%mod;}
inline signed query0(int n){
	rr int ans=0;
	for (rr int l=1,r;l<=n;l=r+1)
		r=n/(n/l),Mo(ans,(r-l+1ll)*(n/l)%mod);
	return ans;
}
inline signed query1(int n){
	rr int ans=0;
	for (rr int l=1,r;l<=n;l=r+1)
	    r=n/(n/l),Mo(ans,(1ll*(l+r)*(r-l+1)%mod)*(1ll*(n/l)*(n/l+1)%mod)%mod);
	return ans;
} 
inline signed query(int n){
	rr int ans=0;
	for (rr int l=1,r;l<=n;l=r+1){
		r=n/(n/l),Mo(ans,mo(sf(r),sf(l-1))*query0(n/l)%mod);
		Mo(ans,(r-l+1ll)*query1(n/l)%mod);
	}
	return 6ll*ans%mod;
}
signed main(){
	rr int l,r; scanf("%d%d",&l,&r);
	return !PRintf("%d",mo(query(r),query(l-1)));
}

脚本宝典总结

以上是脚本宝典为你收集整理的#整除分块#洛谷 3636 曲面全部内容，希望文章能够帮你解决#整除分块#洛谷 3636 曲面所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。