P8762题解

Light_az · 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;
}