自动搬运

查看原文

来自洛谷，原作者为

	Light_az florr.io 同名 || 莱特阿哲

搬运于2025-08-24 22:42:12，当前版本为作者最后更新于2023-01-09 14:10:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

怎么其他题解这么不人性化，这道题可以不需要前缀和，利用数学思想就能轻松过关。

首先，我们的任务是求出 $l$ 和 $r$ 所在的行坐标和列坐标，对于行坐标，我们可以手写一个二分查找，通过枚举前 $mid$ 行以前的数的个数来判断 $l$ 和 $r$ 是否在这一行：

ll Find(ll n){
	ll l=1,r=1000000;
	while(l<r){
		ll mid=(l+r)/2;//mid代表行
		if((1+mid)*mid/2>=n) r=mid;//求第mid行及以前的数的个数
		else l=mid+1;
	}
	return r;
}

然后我们得知了 $n$ 的行数，那么列数就是 n-Find(n-1)，此时我们已经得知了 $n$ 的坐标，现在我们可以求 $l$ 和 $r$ 的区间和了。

首先我们要知道如何求前 $n$ 行的和，我们可以使用前 $n$ 行求和函数：

ll Ans(ll n){
	return n*(n+1)/6*(n+2)/6;//前 n 行都是等差数列，合起来得出以下公式
}

之后我们要求第 $n$ 行的和，也就是 1 一直数到 $n$ 的横坐标的和，我们使用高斯公式：

ll f(ll n){
	return (1+n)*n/2;//（首项+末项）*项数/2
}

最后，我们已经得到了前 $l$ 个数和前 $r$ 个数的和，我们只需要把它们相减就可以得出答案，当然，保险起见，我们要使用 unsigned long long，下面是完整代码：

#include<bits/stdc++.h>
#define ll unsigned long long
#define F(i,a,b) for (int i=a;i<=b;i++)
#define Test ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
const int N=1e7+10,NN=1e4+10;
ll n,m,k,x,y,u,v,w,cnt=0,ans=0,t=0,l,r,len,T;
ll mini=INT_MAX,maxi=0,Mod;
string s1,s2;
ll a[5];
ll Find(ll n){//二分
	ll l=1,r=10000000;
	while(l<r){
		ll mid=(l+r)/2;
		if((1+mid)*mid/2>=n) r=mid;
		else l=mid+1;
	}
	return r;
}
ll f(ll n){//高斯公式
	return (1+n)*n/2;
}
ll Ans(ll n){//前 n 行的和
	return n*(n+1)*(n+2)/6;
}
int main(){
	Test;
	cin>>T;
	while(T--){
		cin>>l>>r;
		a[1]=l-f(Find(l)-1);//前 l 行
		a[2]=r-f(Find(r)-1);//前 r 行
		ll ans1=Ans(Find(l)-1)+a[1]*(a[1]-1)/2;//前 l 个数的和
		ll ans2=Ans(Find(r)-1)+(a[2]+1)*a[2]/2;//前 r 个数的和
		cout<<ans2-ans1<<"\n";
	}
	return 0;
}