题目描述
给定 \(L,R\)，问 \(L \leq x \leq R\) 中有多少个数 \(x\) 满足存在整数 \(y,z\) 使得 \(x=y^2-z^2\)。
输入格式
输入一行包含两个整数 \(L,R\)，用一个空格分隔。
输出格式
输出一行包含一个整数满足题目给定条件的 \(x\) 的数量。
样例输入
1 5
样例输出
4
提示
对于所有评测用例，\(1 \leq L \leq R \leq 10^9\)。
通过平方差公式可得： \(x=(y+z)\times (y-z)\)
两个括号里的奇偶性相同，这是显而易见的
那么分情况讨论
- 若都是奇数，那么 \(x\) 也为奇数，此时只需要把 \(x\) 拆分成 \(1\) 和它本身即可
- 若都是偶数，那么 \(x\) 也为偶数，并且因为两个括号里的数都包含因数 \(2\) ，所以 \(x\) 必定是 \(4\) 的倍数 ，此时只需要把 \(x\) 拆分成 \(1\) 和它本身即可
问题便转化成了在 \(L\) 到 \(R\) 的区间里，有多少个奇数或 \(4\) 的倍数
固然可以枚举一遍，时间复杂度为 \(O(R-L+1)\) ，但还可以优化
不难看出，答案其实就是从 \(1\) 到 \(R\) 这个区间里满足条件的数的个数，减去从 \(1\) 到 \(L-1\) 的个数（有点前缀和的意思）
奇数的个数就是： \(\frac{x+1}{2}\) （ \(+1\) 代表向上取整）
\(4\) 的倍数的个数就是： \(\frac{x}{4}\)
\(Code:\)
#include<bits/stdc++.h>
using namespace std;
int l,r;
int find(int x){
int a=(x+1)/2;
int b=x/4;
return a+b;
}
int main()
{
scanf("%d%d",&l,&r);
printf("%d",find(r)-find(l-1));
return 0;
}