您的当前位置：首页 hi.123

hi.123

来源：百家汽车网

123

题目描述

小蓝发现了一个有趣的数列, 这个数列的前几项如下:

$\ldots$

小蓝发现, 这个数列前 $1$ 项是整数 $1$ , 接下来 $2$ 项是整数 $1$ 至 $2$ , 接下来 $3$ 项是整数 $1$ 至 $3$ , 接下来 $4$ 项是整数 $1$ 至 $4$ , 依次类推。

小蓝想知道, 这个数列中, 连续一段的和是多少。

输入格式

输入的第一行包含一个整数 $T$ , 表示询问的个数。

接下来 $T$ 行, 每行包含一组询问, 其中第 $i$ 行包含两个整数 $l_{i}$ 和 $r_{i}$ , 表示询问数列中第 $l_{i}$ 个数到第 $r_{i}$ 个数的和。

输出格式

输出 $T$ 行, 每行包含一个整数表示对应询问的答案。

样例 #1

样例输入 #1

样例输出 #1

1
4
8

提示

对于 $\%$ 的评测用例, $\leq T \leq 30,1 \leq l_{i} \leq r_{i} \leq 100$ 。

对于 $\%$ 的评测用例, $\leq T \leq 100,1 \leq l_{i} \leq r_{i} \leq 1000$ 。

对于 $\%$ 的评测用例, $\leq T \leq 1000,1 \leq l_{i} \leq r_{i} \leq 10^{6}$ 。

对于 $\%$ 的评测用例, $\leq T \leq 10000,1 \leq l_{i} \leq r_{i} \leq 10^{9}$ 。

对于 $\%$ 的评测用例, $\leq T \leq 1000,1 \leq l_{i} \leq r_{i} \leq 10^{12}$ 。

对于 $\%$ 的评测用例, $\leq T \leq 10000,1 \leq l_{i} \leq r_{i} \leq 10^{12}$ 。

对于所有评测用例, $\leq T \leq 100000,1 \leq l_{i} \leq r_{i} \leq 10^{12}$ 。

蓝桥杯 2021 国赛 A 组 E 题（B 组 F 题，C 组 F 题）。

Code

// #include <iostream>
// #include <algorithm>
// #include <cstring>
// #include <stack>//栈
// #include <deque>//堆/优先队列
// #include <queue>//队列
// #include <map>//映射
// #include <unordered_map>//哈希表
// #include <vector>//容器，存数组的数，表数组的长度
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
typedef long long ll;

void solve()
{
    ll l,r;
    cin>>l>>r;

    ll n=ceil((-1+sqrt(1+8*l))/2.0);//行数
    ll m=ceil((-1+sqrt(1+8*r))/2.0);

    ll el=(n-1)*n*(n+1)/6;//前n-1行的前缀和
    ll er=(m-1)*m*(m+1)/6;

    ll sl=l-n*(n-1)/2;//第n行多余的数
    ll sr=r-m*(m-1)/2;

    cout<<er-el+(sr+1)*sr/2-(sl-1)*sl/2<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    ll t;
    cin>>t;
    while(t--) solve();
    
    return 0;
}

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文