P9231 [蓝桥杯 2023 省 A] 平方差--巧妙统计奇数的个数！

题目

分析

看题目字挺少，条件，目的非常清晰，我脑子中的暴力算法直接涌现出来了^ ^，都是我看来一下L，R的范围QAQ

分享大佬题解

将x表示为y² - z²，可以因式分解为x = (y+z)(y-z)

设a = y+z，b = y-z，则x = a*b

则a+b=2Y，那么a和b必须同奇偶（因为它们的和是2y，差是2z，必须同为偶数）

因此有两种情况：

奇数：当a和b都是奇数时，x是奇数

4的倍数：当a和b都是偶数时，x必然是4的倍数（为什么是4的倍数，以为偶数都是2的倍数，2个偶数的乘积就是4的倍数了）

综上所述：

我们所需要的数得满足 是奇数或者是4的倍数

所以最总答案为[L,R]区间中奇数和四的倍数的个数

统计奇数个数

return (x+1)/2;

这个+1操作非常巧妙

为什么能统一处理奇偶？

众所周知，奇数的个数 ≈ 总数量的一半，但需要根据 x 的奇偶性做微调。

无论是奇数还是偶数，+1 操作都能保证：

当 x 是奇数时，结果正好是中间值（无小数）
当 x 是偶数时，结果自动舍去小数部分（对正确答案无影响）

巧妙利用了 C++ 中，(x + 1) / 2 的整数除法会自动向下取整。例如：

x=5 → 6/2=3（整数）
x=6 → 7/2=3（舍去 0.5）

统计4的倍数个数

return x/4;

代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>

#include <cctype>
using namespace std;
//求0~x一共有多少个奇数
int ji(int x) {
	if (x == 0)
		return 0;
	else
		return (x + 1) / 2;
}
//求0~x一共有多少个偶数
int ou(int x) {
	return x / 4;
}

int main() {
	int l, r;
	cin >> l >> r;
	cout << ji(r) - ji(l - 1) + ou(r) - ou(l - 1) << endl;
//l-1为什么？以为题中是个闭区间，为了不把l这个值减去，就只能得算到l-1
	return 0;
}