🌟数学规律 + 分类讨论 + 前缀和思想
🍎解题思路
1.对于原题中的$x = y^2 - z^2$,发现$x$只要满足是奇数或者4的倍数就是一种答案,严格证明如下👇
由于 $x = (y + z) * (y - z)$
不妨令$A = (y + z)$ ,$B = (y - z)$
那么有 $A - B = y + z - y + z = 2z$
不难看出, $2z$ 为偶数的一般表达形式。也就是说,对于任意两个整数的平方差若能凑出 $x$,那么这两个整数相差一定为偶数,相应的,上式A、B的组合形式也只能是奇*奇
或者偶*偶
。
对于所有的奇*奇
的形式,可以表示为奇数其本身和1相乘,相差一定为偶数,所以所有的奇数满足条件。
其次,对于所有偶*偶
的形式,两个偶数相乘一定是4的倍数。
2.有了以上结论,由于题目范围 $10^9$,显然遍历区间会超时,我们考虑用除法来求解奇数和4的倍数的个数,其中奇数利用 $x/2$ 上取整,4的倍数利用 $x/4$ 下取整,举点儿例子就可以轻松发现此规律👇
$x/2$上取整可以获得$[1,x]$奇数个数: $⌈9 / 2⌉ = 5$($1,3,5,7,9$为$[1,x]$的奇数)
$x/4$下取整可以获得$[1,x]$中$4$的倍数的个数$⌊5 / 4⌋ = 1$(只有$4$一个为$4$的倍数)
3.分别获取$[1…r]$和$[1…l-1]$区间内两种数字个数做差减去交集,即可得到答案。
🍭技巧
1.两乘积若做差可以消元,那么做差看看,发现两者之间的规律之后,从而推出$x$的规律和性质
2.奇数利用 $x/2$ 上取整,4的倍数利用 $x/4$ 下取整可以分别获 $[1,x]$ 内的数量
🍇时间复杂度
$O(1)$
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//获取[1...x]中 4的倍数 和 奇数的个数,前者下取整,后者上取整
LL get_sum(LL x)
{
return x / 4 + (x + 1) / 2;
}
int main()
{
LL l, r;
cin >> l >> r;
cout << get_sum(r) - get_sum(l - 1); //减去集合重合的部分即可
return 0;
}
https://www.acwing.com/solution/content/202963/
可以看看我的思路
狂推
为什么能确定y,z的范围,y,z一定在[l,r]这个区间里吗?
niubi
大佬牛
对于任意两个整数的平方差若能凑出 x,那么这两个整数相差一定为偶数
这也只是能看出换元后的两个数相差一个偶数吧?单纯的y、z怎么看出来相差偶数的?
博主说的就是换元后的A,B相差偶数吧。所以AB肯定同时为奇数或者同时为偶数
nb
orz
nb
orz
妙啊