【数学+前缀和】第十四届蓝桥杯省赛C++ A组《平方差》（c++）

 【问题描述】

   给定 L,R，问 L≤x≤R 中有多少个数 x 满足存在整数 y,z 使得 x=y的平方−z的平方。

【输入格式】

   输入一行包含两个整数 L,R，用一个空格分隔。

【输出格式】

   输出一行包含一个整数满足题目给定条件的 x 的数量。

【数据范围】

   对于 40% 的评测用例，1≤L,R≤5000；
   对于所有评测用例，1≤L≤R≤10的9次方。

【输入样例】

【输出样例】

【样例解释】

【思路】

   对前缀和不了解的可以参考【模板】AcWing795.《前缀和》(C++)

   将x = y的平方-z的平方用平方差公式拆开可以得到 x = (y+z) * (y-z) 。

   令 A = y + z , B = y - z , A - B = 2z; 由于A - B 的差一定为奇数，所以A 和 B只能全为全奇数或全

   为偶数。我们把x  = A * B 并且A和B全是奇数的情况看为一个奇数和1的乘积，一个奇数减去1满

   足结果为偶数的条件，当A和B全为偶数的时候结果一定为4的倍数。

   由此转换为求出两个区间内所有4的倍数的个数以及奇数的个数之和，然后计算[1,r]-[1,l-1]即可。

【代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL compute(LL x){
    //计算[1，x]内是4的倍数的数以及所有奇数的和
    return x / 4 + (x + 1) / 2;
}
int main()
{
    LL l,r;
    cin>>l>>r;
    //前缀和减去重合部分
    cout<<compute(r)-compute(l-1);
}