問題描述
格式輸入
輸入一行包含兩個整數(shù) L, R，用一個空格分隔。
格式輸出
輸出一行包含一個整數(shù)滿足題目給定條件的 x 的數(shù)量。
樣例輸入
1 5
樣例輸出
4
評測用例規(guī)模與約定
對于 40% 的評測用例，L R ≤ 5000 ；
對于所有評測用例，1 ≤ L ≤ R ≤ 10^9 。
解析
暴力沒說的，y肯定在l-r之間。同時要想到x=（y+z）（y-z）那么x就只能是y+z的倍數(shù)。 啊啊啊，感謝提醒，有可能一個數(shù)還有不同的組合。
1.使用了兩層循環(huán)，分別用于枚舉 y 和 z。對于每一個 y 和 z，都可以根據(jù)題目給定的公式
x
=
y
2
?
z
2
x=y^2-z^2
x=y2?z2 計算出對應(yīng)的 x 值。如果 x 值在區(qū)間 [L, R] 中，那么就將答案加一。最后輸出答案即可。
需要注意的是，由于輸入范圍很大，因此對應(yīng)的數(shù)據(jù)類型也需要選擇比較大的類型，這里使用了 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; // 根據(jù)公式計算出 x
if (x >= L&&x<=R) ans++; // 如果 x 在區(qū)間 [L, R] 中，累加答案
}
}
cout << ans << endl; // 輸出答案
return 0;
}
~~ 改后 過40% 肯定是超時了，第一個點(diǎn)可以過，大佬們看看怎么不會超時。
#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; // 根據(jù)公式計算出 x
if(x>=l&&x<=r) a[x]++;//x的出現(xiàn)存到數(shù)組里
}
}
for (long long i = 1; i <= r; i++)
{
if (a[i] > 0) ans++;
}
cout << ans << endl; // 輸出答案
return 0;
}
補(bǔ)的在大佬們點(diǎn)撥下:一些數(shù)論的知識，算出不能表示的數(shù)（不能被4整除可以被2整除）的個數(shù)減去。O(1)復(fù)雜度。文章來源：http://www.zghlxwxcb.cn/news/detail-413570.html
#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;
}
以個人刷題整理為目的，如若侵權(quán)，請聯(lián)系刪除~文章來源地址http://www.zghlxwxcb.cn/news/detail-413570.html
到了這里，關(guān)于第十四屆藍(lán)橋杯大賽軟件賽省賽 C/C++ 大學(xué) A 組 C題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
