题目描述
给定
L
L
L和
R
R
R,问
L
≤
x
≤
R
Lleq x leq R
L≤x≤R中有多少个数
x
x
x满足存在整数
y
y
y,
z
z
z使得
x
=
y
2
−
z
2
x = y^{2} – z^{2}
x=y2−z2。
输入格式
输入一行包含两个整数
L
L
L,
R
R
R,用一个空格分隔。
输出格式
输出一行包含一个整数满足题目给定条件的
x
x
x 的数量。
输入输出样例
输入 #1
1 5
输出 #1
4
说明/提示
【样例说明】
-
1
=
1
2
−
0
2
1 = 1^{2} −0 ^{2}
-
3
=
2
2
−
1
2
3 = 2^{2}−1^{2}
-
4
=
2
2
−
0
2
4 = 2^{2}−0^{2}
-
5
=
3
2
−
2
2
5 = 3^{2}−2^{2}
题解
本篇题解适合没有思路的人群,对于数学较好的人来说就会显得比较繁琐和臃肿。
乍一看挺简单,但是如果数学不是太好的人就没有思路,所以我们来看一下思路:
首先拿到这个题,先将
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)
我们让
a
=
服务器托管网
y
+
z
a = y + z
a=y+z 然后
b
=
y
−
z
b = 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
a
a和
b
b
b替换掉原来的式子:
x
=
a
∗
b
x = a * b
x=a∗b
此时这个式子中的x是确定值,
a
a
a和
b
b
服务器托管网
b是随机量。如果仅仅是这样是不行的,
a
a
a和
b
b
b是有限制条件的,当我们找到
a
a
a和
b
b
b的限制条件,我们距离解题就不远了。
那么
a
a
a和
b
b
b的限制条件是什么呢?
继续观察这个式子:
{
a
=
y
+
z
b
=
y
−
z
begin{cases} a = y + z \ b = y – z end{cases}
{a=y+zb=y−z
相加得到
a
+
b
=
2
y
a + b = 2y
a+b=2y
y
y
y是一个随机量,但是
y
y
y是一个整数,又因为是
2
y
2y
2y,因此发现
a
+
b
a + b
a+b 的值一定是个偶数。
什么样的数相加为偶数呢?
- 奇 + 奇 = 偶
- 偶 + 偶 = 偶
只有以上两种情况。
因此会发现,
a
a
a 和
b
b
b 的奇偶性相同。
因此,对于
x
=
a
∗
b
x = a * b
x=a∗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
L
L到
R
R
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
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;
}
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net