P10416 题解

yitian_ · 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;  // 表示程序成功完成
}