[蓝桥杯 2023 省 A] 平方差

题目描述

给定 $L,R$，问 $L \leq x \leq R$ 中有多少个数 $x$ 满足存在整数 $y,z$ 使得 $x=y^2-z^2$。

输入格式

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

输出格式

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

样例 #1

样例输入 #1

1 5

样例输出 #1

4

提示

【样例说明】

• $1=1^2-0^2$
• $3=2^2-1^2$
• $4=2^2-0^2$
• $5=3^2-2^2$

【评测用例规模与约定】

对于 $40 \%$ 的评测用例，$L,R \leq 5000$；

对于所有评测用例，$1 \leq L \leq R \leq 10^9$。

第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 C

#include<bits/stdc++.h>
using namespace std;
bool mark[105];
int r,l;
// 打表找规律：奇数+4的倍数
void find()
{
    for(int i=0;i<=100;i++){
        for(int j=0;j<=100;j++){
         for(int z=0;z<=100;z++){
            if(!mark[i]){
                if(i == j*j - z*z){
                    cout << i << endl;
                    mark[i] = true;
                 }
             }
         }
    }
}
}
int main(){
    find();
    cin>>l>>r;
    cout<<(r+1)/2-(l-1+1)/2+r/4-(l-1)/4;
    return 0;
}