【问题描述】
给定 L,R,问 L≤x≤R 中有多少个数 x 满足存在整数 y,z 使得 x=y的平方−z的平方。
【输入格式】
输入一行包含两个整数 L,R,用一个空格分隔。
【输出格式】
输出一行包含一个整数满足题目给定条件的 x 的数量。
【数据范围】
对于 40% 的评测用例,1≤L,R≤5000;
对于所有评测用例,1≤L≤R≤10的9次方。
【输入样例】
1 5
【输出样例】
4
【样例解释】
【思路】
对前缀和不了解的可以参考【模板】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);
}