自动搬运

查看原文

来自洛谷，原作者为

	yitian_ 高估 T3 以至于打个深搜就睡觉去了/kel

搬运于2025-08-24 22:57:46，当前版本为作者最后更新于2024-05-08 17:42:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

本题将有 $T$ 组询问，每组询问给定一个区间 $[L,R]$，需要求出有多少组 $X,Y,Z$ 在区间范围内并满足 $X+Y=Z$。对于所有评测用例，$1\leq L\leq R\leq10^9$。

思路

由于数据范围为 $1\leq L\leq R\leq10^9$，暴力枚举将是不可行的，需要找规律。

因为 $X$ 和 $Y$ 的最小值为 $L$，所以 $Z$ 的最小值为 $2L$。

• 当 $Z=2L$ 时，$X=L,Y=L$，共一组。

• 当 $Z=2L+1$ 时，$X=L,Y=L+1$ 或 $X=L+1,Y=L$，共两组。

• 当 $Z=2L+2$ 时，$X=L,Y=L+2$ 或 $X=L+1,Y=L+1$ 或 $X=L+2,Y=L$，共三组。

• 当 $Z=2L+3$ 时，$X=L,Y=L+3$ 或 $X=L+1,Y=L+2$ 或 $X=L+2,Y=L+1$ 或 $X=L+3,Y=L$，共四组。

• $\cdots$

• 当 $Z=2L+n=R$ 时，可推导出共有 $n+1$ 种满足条件的 $X,Y,Z$ 组合。变形可得 $n=R-2L$。所以此时满足条件的 $X,Y,Z$ 有 $R-2L+1$ 种。

答案已经很明显了，为一个公差为 $1$ 的等差数列之和。即 $1+2+3+\cdots+(R-2L+1)$。

因为公差为 $1$，首项为 $1$，末项为 $R-2L+1$，所以该等差数列的项数为 $R-2L+1$。

所以，该等差数列之和为 $\dfrac{(R-2L+1)\times(R-2L+2)}{2}$。

需要注意的是，因为 $Z$ 最小为 $2L$，所以 $R<2L$ 时将没有任何一组满足条件的 $X,Y,Z$。因此需要先判断 $R$ 是否小于 $2L$。如果是，输出 $0$ 并跳过循环的其余部分，进行下一组询问。

C++ 代码实现

#include<bits/stdc++.h>  // 包含所有标准 C++ 库
using namespace std;  

int main()
{
    long long ans,t;
    cin >> t;  // 输入测试用例的数量
    while(t--)
    {
        long long l,r,n,m;
        cin >> l >> r;  // 输入 l 和 r 的值
        if(r<2*l)
        {
            cout << 0 << endl;  // 输出 0 并换行
            continue;  // 跳过循环的其余部分
        }
        // 计算项数以及首项与末项的和
        n=r-2*l+1;
        m=r-2*l+2;
        ans=n*m/2;
        // 输出答案
        cout << ans << endl;  // 输出 ans 的值并换行
    }
    return 0;  // 表示程序成功完成
}