题目描述
小蓝发现了一个有趣的数列, 这个数列的前几项如下:
1,1,2,1,2,3,1,2,3,4,…1,1,2,1,2,3,1,2,3,4,…
小蓝发现, 这个数列前 11 项是整数 11 , 接下来 22 项是整数 11 至 22 , 接下来 33 项是整数 11 至 33 , 接下来 44 项是整数 11 至 44 , 依次类推。
小蓝想知道, 这个数列中, 连续一段的和是多少。
输入格式
输入的第一行包含一个整数 TT, 表示询问的个数。
接下来 TT 行, 每行包含一组询问, 其中第 ii 行包含两个整数 lil**i 和 rir**i, 表示 询问数列中第 lil**i 个数到第 rir**i 个数的和。
输出格式
输出 TT 行, 每行包含一个整数表示对应询问的答案。
输入输出样例
输入 #1
3
1 1
1 3
5 8
输出 #1
1
4
8
解析
首先我们观察这个数列，我们可以把他分解成一个三角形的二维数组
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
因此我们可以得到以下性质：
第n行的和为: (n + 1) * n / 2（高斯公式）
前n行的和为：n * (n + 1) * (n + 2) / 6
我们可以使用类似于前缀和的方法来解题，既前r个数字和减去前l个数字和。
我们该如何来求数字和呢？如果我们知道他所在的行数以及他所在的列数，那么我们就可以使用上述公式来求解，既：
前n-1行的和 再加上 1到这一列的和
现在的问题转到了如何求行和列，对于行数我们可以枚举行数来进行二分求解
int Find(int x)
{int l = 0, r = 100000000;while (l < r){int mid = l + (r - l) / 2;if ((mid + 1) * mid / 2 >= x)r = mid;elsel = mid + 1;}return r;
}
同样的道理，我们知道了它的行数以及它一维的位置，可以得出它的列坐标
列坐标 = index - 行 * （行 + 1）/ 2
代码
#include<bits/stdc++.h>
using namespace std;
#define int long longint l, r, t;
int indexl, indexr;
int suml, sumr;int Find(int x)
{int l = 0, r = 100000000;while (l < r){int mid = l + (r - l) / 2;if ((mid + 1) * mid / 2 >= x)r = mid;elsel = mid + 1;}return r;
}int f(int x)//高斯公式
{return (x + 1) * x / 2;
}int sumn(int x)
{return x * (x + 1) * (x + 2) / 6;
}signed main()
{cin >> t;while (t--){cin >> l >> r;indexl = l - f(Find(l) - 1);indexr = r - f(Find(r) - 1);suml = sumn(Find(l) - 1) + indexl * (indexl - 1) / 2;sumr = sumn(Find(r) - 1) + indexr * (indexr + 1) / 2;cout << sumr - suml << endl;}return 0;
}