P8762 [蓝桥杯 2021 国 ABC] 123 题解

· · 题解

就像其他题解那样，我们将这个数列分解成一个二维的三角形，大概长这样：

1
1 2
1 2 3
1 2 3 4
...

来推导几个公式。

第 i 行的数字总和：

1+2+...+i=\frac{1+2+...+i+1+2+...+i}{2}=\frac{(1+i)+(2+i-1)+...+(i+1)}{2}=\frac{i\times(i+1)}{2}

前 i 行的数字总和：

\frac{1\times 2}{2}+\frac{2\times 3}{2}+...+\frac{i\times (i+1)}{2}=\frac 1 2 (1\times 2+2\times 3+...+i\times (i+1)) =\frac 1 6 \times (1\times 2\times 3+2\times 3\times (4-1)+...+i\times (i+1)\times(i+2-i+1))=\frac 1 6 \times i\times (i+1)\times (i+2)

于是我们用类似前缀和的思想，把问题拆成几个式子加加减减即可。

这里我们还需要一个函数来求某个数字在哪一行，二分即可，实现如下：

long long fd(long long x)
{
    long long l=1,r=10000000,ans;
    while(l<=r)
    {
        long long mid=(l+r)/2;
        if(mid*(mid+1)/2<x)l=mid+1;
        else 
        {
            r=mid-1;
            ans=mid;
        }
    }
    return ans;
}

全部代码如下：

#include<bits/stdc++.h>
using namespace std;
long long n,l,r,ans,t1,t2,st,ed,k1,k2;
long long fd(long long x)
{
    long long l=1,r=10000000,ans;
    while(l<=r)
    {
        long long mid=(l+r)/2;
        if(mid*(mid+1)/2<x)l=mid+1;
        else 
        {
            r=mid-1;
            ans=mid;
        }
    }
    return ans;
}
int main()
{
    scanf("%lld",&n);
    while(n--)
    {
        scanf("%lld%lld",&l,&r);
        st=fd(l),ed=fd(r);//找出行
        t1=l-st*(st-1)/2;//划归为几个完整的行，方便计算
        t2=r-ed*(ed-1)/2;
        k1=(st-1)*st*(st+1)/6;//求出两个行的前缀和
        k2=(ed-1)*ed*(ed+1)/6;
        cout<<k2-k1+(t2+1)*t2/2-(t1-1)*t1/2<<endl;//运算，把刚才处理掉的补上
    }
}