算法竞赛例题讲解：平方差 第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 C平方差

题目描述

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

输入格式

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

输出格式

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

输入输出样例

输入 #1

1 5
1

输出 #1

4
1

说明/提示

【样例说明】

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

题解

本篇题解适合没有思路的人群，对于数学较好的人来说就会显得比较繁琐和臃肿。

乍一看挺简单，但是如果数学不是太好的人就没有思路，所以我们来看一下思路：

首先拿到这个题，先将$x=y^2-z^2$化简：

$$x=(y+z)(y-z)$$

我们让 $a=y+z$ 然后 $b=y-z$ ,得到如下式子：

{ a = y + z b = y − z

$$\begin{cases} a = y + z \\ b = y - z \end{cases}$$ {a=y+zb=y−z​

用$a$和$b$替换掉原来的式子：

$$x=a\ast b$$

此时这个式子中的x是确定值，$a$和$b$是随机量。如果仅仅是这样是不行的，$a$和$b$是有限制条件的，当我们找到$a$和$b$的限制条件，我们距离解题就不远了。

那么$a$和$b$的限制条件是什么呢？

继续观察这个式子：

{ a = y + z b = y − z

$$\begin{cases} a = y + z \\ b = y - z \end{cases}$$ {a=y+zb=y−z​

相加得到

$$a+b=2y$$

$y$是一个随机量，但是$y$是一个整数，又因为是$2y$，因此发现 $a+b$ 的值一定是个偶数。

什么样的数相加为偶数呢？

• 奇 + 奇 = 偶
• 偶 + 偶 = 偶

只有以上两种情况。

因此会发现，$a$ 和 $b$ 的奇偶性相同。

因此，对于$x=a\ast b$ ，我们需要将拆分成奇偶性相同的两个随机量。

由于：

• 奇 * 奇 = 奇
• 偶 * 偶 = 偶

奇 * 偶 的情况不讨论，因为不存在

所以发现，x的奇偶性不同时，拆分情况是唯一对应的，因此分情况讨论：

• x为奇数时：令a = 1，b为本身。例如：x = 9时，a = 1， b = 9。a，b都为奇数，因此x = 9满足条件。
• x为偶数时：令a = 2，b为x / 2.例如：x = 10时，a = 2， b = 5，但是发现b是奇数，因此x = 10不满足条件。x = 12 是，a = 2， b = 6，都是偶数，因此x = 12满足条件。

我们多举出几个例子之后发现所有的奇数都满足条件。因为我们令b = 本身，而x总是奇数，因此所有的奇数x都满足条件。

对于偶数来说，我们想要让x满足条件时，需要让x / 2满足偶数的条件，也就是满足x / 2是2的倍数的条件，所以发现，a = 2， b 是 2的倍数，所以x是4的倍数。所以只要满足x为4的倍数，就满足条件。

总的来说，我们需要在$L$到$R$中找出所有奇数的个数和4的倍数的数的个数

程序代码如下：

// Problem: P9231 [蓝桥杯 2023 省 A] 平方差
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9231
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

/*************************************************************************
	> Author:Royi 
	> Mail:royi990001@gmail.com 
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
// 返回的是从0到x的奇数的个数
int f(int x) {
	if (!x) return 0;
	else return (x + 1) / 2;
}

//返回的是从0到x的4的倍数的个数
int g(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 << f(r) - f(l - 1) + g(r) - g(l - 1) << '\n';
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33