P9231 [蓝桥杯 2023 省 A] 平方差 - 洛谷

题目描述

给定 L,R，问 L≤x≤R 中有多少个数 x 满足存在整数 y,z 使得 x=y2−z2。

输入格式

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

输出格式

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

输入输出样例

输入 #1	输出 #1
1 5	4

说明/提示

【样例说明】

• 1=12−02
• 3=22−12
• 4=22−02
• 5=32−22

【评测用例规模与约定】

• 对于 40% 的评测用例，L,R≤5000；
• 对于所有评测用例，1≤L≤R≤109。

第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 C

思路：

数学知识，

1. 奇偶性分析：

   • 情况 1：y 和 z 都是奇数或都是偶数
     • 如果 y 和 z 都是奇数或都是偶数，那么 y−z 和 y+z 的奇偶性相同。
     • 两个奇数或两个偶数相减和相加的结果都是偶数。
     • 因此，x 是两个偶数的乘积，即 x 是 4 的倍数。
   • 情况 2：y 和 z 一奇一偶
     • 如果 y 和 z 一奇一偶，那么 y−z 和 y+z 都是奇数。
     • 两个奇数相乘的结果是奇数。
     • 因此，x 是两个奇数的乘积，即 x 是奇数。

从上述分析可以看出，无论 y 和 z 的奇偶性如何，x=(y−z)×(y+z) 总是可以表示为两个奇偶性相同的数的乘积：

• 如果 y 和 z 的奇偶性相同，x 是两个偶数的乘积（即 4 的倍数）。
• 如果 y 和 z 的奇偶性不同，x 是两个奇数的乘积（即奇数）。

因此，表达式 x=(y−z)×(y+z) 保证了 x 可以被拆分成两个奇偶性相同的数的乘积。

代码如下：
 

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll; 
ll j(ll x)
{if(x == 0)return 0;elsereturn (x+1)/2;
}
ll o(ll x)
{return x/4;
}
int main() 
{ll l,r;cin >> l >> r;cout << j(r) - j(l - 1) + o(r) - o(l - 1); return 0;
}