第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 C题-Toy模板网

这篇具有很好参考价值的文章主要介绍了第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 C题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

问题描述

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

格式输入

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

格式输出

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

样例输入

1 5

样例输出

评测用例规模与约定

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

解析

暴力没说的，y肯定在l-r之间。同时要想到x=（y+z）（y-z）那么x就只能是y+z的倍数。
1.使用了两层循环，分别用于枚举 y 和 z。对于每一个 y 和 z，都可以根据题目给定的公式 $x=y^2-z^2$ 计算出对应的 x 值。如果 x 值在区间 [L, R] 中，那么就将答案加一。最后输出答案即可。
需要注意的是，由于输入范围很大，因此对应的数据类型也需要选择比较大的类型，这里使用了 long long 类型。啊啊啊，感谢提醒，有可能一个数还有不同的组合。

参考程序

~~
#include
#include
using namespace std;
typedef long long LL; // 定义 long long 类型为 LL
int main()
{
LL L, R;
cin >> L >> R;
int ans = 0;
for (LL i = 1; i <= R; i++) { // 遍历所有的 y
for (LL j = 0; j <= i; j++) { // 遍历所有的 z
LL x = i * i - j * j; // 根据公式计算出 x
if (x >= L&&x<=R) ans++; // 如果 x 在区间 [L, R] 中，累加答案
}
}
cout << ans << endl; // 输出答案
return 0;
}
~~ 改后过40% 肯定是超时了，第一个点可以过，大佬们看看怎么不会超时。

#include<iostream>
using namespace std;
#include<vector>
typedef long long ll;
ll a[100000010];
int main()
{
    ll l, r;
    cin >> l >> r;
    int ans = 0;
    for (ll i = 1; i <= r; i++) { // 遍历所有的 y
        for (ll j = 0; j <= i; j++) { // 遍历所有的 z
            ll x = i * i - j * j; // 根据公式计算出 x
           if(x>=l&&x<=r) a[x]++;//x的出现存到数组里
        }
    }
    for (long long i = 1; i <= r; i++)
    {
        if (a[i] > 0) ans++;
    }
    cout << ans << endl; // 输出答案
    return 0;
}

补的在大佬们点拨下:一些数论的知识，算出不能表示的数（不能被4整除可以被2整除）的个数减去。O(1)复杂度。

#include <iostream>
using namespace std;
int main() {
    int L, R;
    cin >> L >> R;
    int cnt = (R / 2) - ((L - 1) / 2) - (R / 4) + ((L - 1) / 4);
    cout << R-L+1-cnt<< endl;
    return 0;
}