题解：P10416 [蓝桥杯 2023 国 A] XYZ

Lele_Programmer · 2024-05-08 21:57:30 · 题解

P10416 题解

思路

给出 L 和 R，对于此区间内第一个存在可行 X,Y 的 Z 值，最小为 L \times 2，证明：因为 X,Y 最小只能取 L，所以最小 Z 值为 L \times 2。

所以，若 L \times 2 > R，无解，输出 0。

对于一个存在可行解的 Z (Z<R)，设 Z 存在 K 组 X,Y，则 Z+1 存在 K+1 组 X,Y，证明：对于一个 Z 的所有 X 值分别为 L 到 Z-L 之间的正整数，设总共有 K 个解，那么同理，Z+1 的所有 X 值分别为 L 到 Z+1-L 之间的正整数，即 K+1 个解。

所以，问题就变成了求 \sum\limits_{i=1}^{R-L \times 2+1}i。

记得开 long long！

代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

int T,l,r;

signed main() {
    scanf("%lld",&T);
    while (T--) {
        scanf("%lld %lld",&l,&r);
        if (l*2>r) {
            puts("0");
            continue;
        }
        int a=l*2;
        int b=r-a+1;
        printf("%lld\n",(1ll+b)*b/2ll);
    }
    return 0;
}