小蓝发现了一个有趣的数列, 这个数列的前几项如下:
1 , 1 , 2 , 1 , 2 , 3 , 1 , 2 , 3 , 4 , … 1,1,2,1,2,3,1,2,3,4, \ldots 1,1,2,1,2,3,1,2,3,4,…
小蓝发现, 这个数列前 1 1 1 项是整数 1 1 1 , 接下来 2 2 2 项是整数 1 1 1 至 2 2 2 , 接下来 3 3 3 项是整数 1 1 1 至 3 3 3 , 接下来 4 4 4 项是整数 1 1 1 至 4 4 4 , 依次类推。
小蓝想知道, 这个数列中, 连续一段的和是多少。
输入的第一行包含一个整数 T T T, 表示询问的个数。
接下来 T T T 行, 每行包含一组询问, 其中第 i i i 行包含两个整数 l i l_{i} li 和 r i r_{i} ri, 表示 询问数列中第 l i l_{i} li 个数到第 r i r_{i} ri 个数的和。
输出 T T T 行, 每行包含一个整数表示对应询问的答案。
3
1 1
1 3
5 8
1
4
8
对于 10 % 10 \% 10% 的评测用例, 1 ≤ T ≤ 30 , 1 ≤ l i ≤ r i ≤ 100 1 \leq T \leq 30,1 \leq l_{i} \leq r_{i} \leq 100 1≤T≤30,1≤li≤ri≤100 。
对于 20 % 20 \% 20% 的评测用例, 1 ≤ T ≤ 100 , 1 ≤ l i ≤ r i ≤ 1000 1 \leq T \leq 100,1 \leq l_{i} \leq r_{i} \leq 1000 1≤T≤100,1≤li≤ri≤1000 。
对于 40 % 40 \% 40% 的评测用例, 1 ≤ T ≤ 1000 , 1 ≤ l i ≤ r i ≤ 1 0 6 1 \leq T \leq 1000,1 \leq l_{i} \leq r_{i} \leq 10^{6} 1≤T≤1000,1≤li≤ri≤106 。
对于 70 % 70 \% 70% 的评测用例, 1 ≤ T ≤ 10000 , 1 ≤ l i ≤ r i ≤ 1 0 9 1 \leq T \leq 10000,1 \leq l_{i} \leq r_{i} \leq 10^{9} 1≤T≤10000,1≤li≤ri≤109 。
对于 80 % 80 \% 80% 的评测用例, 1 ≤ T ≤ 1000 , 1 ≤ l i ≤ r i ≤ 1 0 12 1 \leq T \leq 1000,1 \leq l_{i} \leq r_{i} \leq 10^{12} 1≤T≤1000,1≤li≤ri≤1012 。
对于 90 % 90 \% 90% 的评测用例, 1 ≤ T ≤ 10000 , 1 ≤ l i ≤ r i ≤ 1 0 12 1 \leq T \leq 10000,1 \leq l_{i} \leq r_{i} \leq 10^{12} 1≤T≤10000,1≤li≤ri≤1012 。
对于所有评测用例, 1 ≤ T ≤ 100000 , 1 ≤ l i ≤ r i ≤ 1 0 12 1 \leq T \leq 100000,1 \leq l_{i} \leq r_{i} \leq 10^{12} 1≤T≤100000,1≤li≤ri≤1012 。
蓝桥杯 2021 国赛 A 组 E 题(B 组 F 题,C 组 F 题)。
#include
#define LL long long
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e9 + 10;
const int N = 1e6;
LL sum(LL i){
return i * (i + 1) * (i + 2)/6;
}
LL cal(LL x){
LL left = 0,right = INF,i;
while(left <= right){
LL mid = (left + right)/2;
if(mid * (mid + 1) /2 <= x){
left = mid + 1;
i = mid;
}
else{
right = mid - 1;
}
}
LL j = x - (i + 1) * i/2;
return sum(i) + j * (j + 1)/2;
}
int main(){
int T;
cin >> T;
LL l,r;
while(T--){
cin >> l >> r;
cout << cal(r) - cal(l - 1) << endl;
}
system("pause");
return 0;
}