题目 3142: 蓝桥杯2023年第十四届省赛真题-平方差
时间限制: 2s 内存限制: 320MB 提交: 20234 解决: 3908
题目描述
给定 L, R，问 L ≤ x ≤ R 中有多少个数 x 满足存在整数 y,z 使得 x = y2 − z2。
输入格式
输入一行包含两个整数 L, R，用一个空格分隔。
输出格式
输出一行包含一个整数满足题目给定条件的 x 的数量。
样例输入复制
1 5
样例输出复制
4
提示
1 = 12 − 02 ；
3 = 22 − 12 ；
4 = 22 − 02 ；
5 = 32 − 22 。

对于 40% 的评测用例，LR ≤ 5000 ；
对于所有评测用例，1 ≤ L ≤ R ≤ 109 。

1.分析

        奇数一定可以实现平方差，即（x+1）*(x-1)；

        偶数，如果是除二的结果为偶数也一定是平方差：

        假设a=2*x，x为偶数，d=x-2，d也一定是偶数，则a=（x-d/2+d/2)*(x-d/2-d/2)=x*2；

2.代码

#include<iostream>
#include<cmath>
#include<unordered_map>
using namespace std;
const int MAX = 1010;
int l, r,num;
int main() {
    cin >> l >> r;
    for (int i = l; i <= r; i++) {
        if (i % 2 != 0 || i / 2 % 2 == 0) num++;
    }
    cout << num << endl;
    return 0;
}