本文主要是介绍【洛谷 P9231】[蓝桥杯 2023 省 A] 平方差 题解（数学+平方差公式），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
[蓝桥杯 2023 省 A] 平方差
题目描述
给定 L , R L,R L,R，问 L ≤ x ≤ R L \leq x \leq R L≤x≤R 中有多少个数 x x x 满足存在整数 y , z y,z y,z 使得 x = y 2 − z 2 x=y^2-z^2 x=y2−z2。
输入格式
输入一行包含两个整数 L , R L,R L,R，用一个空格分隔。
输出格式
输出一行包含一个整数满足题目给定条件的 x x x 的数量。
样例 #1
样例输入 #1
1 5
样例输出 #1
4
提示
【样例说明】
- 1 = 1 2 − 0 2 1=1^2-0^2 1=12−02
- 3 = 2 2 − 1 2 3=2^2-1^2 3=22−12
- 4 = 2 2 − 0 2 4=2^2-0^2 4=22−02
- 5 = 3 2 − 2 2 5=3^2-2^2 5=32−22
【评测用例规模与约定】
对于 40 % 40 \% 40% 的评测用例， L , R ≤ 5000 L,R \leq 5000 L,R≤5000；
对于所有评测用例， 1 ≤ L ≤ R ≤ 1 0 9 1 \leq L \leq R \leq 10^9 1≤L≤R≤109。
第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 C
思路
由平方差公式可知， x = y 2 − z 2 x=y^2-z^2 x=y2−z2 可以拆分为 x = ( y + z ) ( y − z ) x=(y+z)(y-z) x=(y+z)(y−z)。易知 ( y + z ) (y+z) (y+z) 和 ( y − z ) (y-z) (y−z) 具有相同的奇偶性。当两者为奇数时，可以是1和x；当两者为偶数时，可以是2和x/2。则 x x x可以是奇数或者4的倍数。因此，程序通过计算区间内奇数的个数和4的倍数的个数，然后将两者相加，得到满足条件的 x x x的个数。
首先定义两个辅助函数 a a a和 b b b，函数 a a a用于求1到x的奇数个数，函数 b b b用于求1到x的4的倍数个数。
然后读取输入的两个数 l l l和 r r r。然后计算满足题目条件的 x x x的数量，即计算 ( a ( r ) − a ( l − 1 ) ) + ( b ( r ) − b ( l − 1 ) ) (a(r) - a(l - 1)) + (b(r) - b(l - 1)) (a(r)−a(l−1))+(b(r)−b(l−1))，其中 a a a和 b b b是前面定义的两个函数。最后输出计算结果。
AC代码
#include <algorithm>
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;// 求1到x的奇数个数
int a(int x) { return (x + 1) >> 1; }// 求1到x的4的倍数个数
int b(int x) { return x / 4; }int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int l, r;cin >> l >> r;cout << (a(r) - a(l - 1)) + (b(r) - b(l - 1)) << "\n";return 0;
}
这篇关于【洛谷 P9231】[蓝桥杯 2023 省 A] 平方差 题解（数学+平方差公式）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
