形式化题目

给定两个整数 $L,R$（$1 \leqslant L \leqslant R \leqslant 10^9$），统计区间 $[L,R]$ 中有多少个整数 $x$，满足存在整数 $y,z$，使得

题面中的 $y,z$ 只需要是整数，可以取 $0$ 或负数，这一点在后面推导时要用到。

样例 $L=1,R=5$ 的可行解如下：

$2$ 不在其中，$[1,5]$ 内共有 $4$ 个满足条件的数。

暴力解法

思路

直接从平方差的形式出发不好枚举：$y,z$ 的取值没有天然上界。把它因式分解就能把问题变简单：

记 $a = y-z,\ b = y+z$，那么 $x = ab$，并且反过来

于是「$x$ 能写成平方差」完全等价于：

存在两个因子 $a,b$，满足 $ab = x$，且 $a+b$ 是偶数（也就是 $a,b$ 同奇偶），并且解出的 $y,z$ 是整数。

$y,z$ 允许为负、越小越负，所以因子 $a,b$ 允许为负也没关系；$x > 0$ 时只要考虑同号因子，枚举 $1 \leqslant a \leqslant \sqrt{x}$ 就覆盖了所有因子对（$b = x/a \geqslant a$）。

这就是暴力解的全部逻辑：对区间里的每个 $x$，枚举它不超过 $\sqrt{x}$ 的因子 $a$，检查 $a + x/a$ 是否为偶数。

代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-03 10:37
 * update_at: 2026-10-03 10:37
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 做法：把 x = y^2 - z^2 看成 (y-z)(y+z)，令 a = y-z >= 1、b = y+z >= a，
// 则 a*b = x 且 a、b 必须同奇偶。反过来，只要找到同奇偶的因子对
// 就能还原 y = (a+b)/2、z = (b-a)/2，所以逐个 x 枚举 a <= sqrt(x) 即可判断。
// 复杂度 O((R-L+1) * sqrt(R))，只适合小范围数据，不能当作正解。
#include <iostream>
using namespace std;

typedef long long ll;

// 判断 x 能否写成两个整数平方的差（y,z 取非负整数即可覆盖所有情况）。
bool can_represent(ll x) {
    if (x == 0) {
        return true; // 取 y = z 即可
    }
    // 枚举较小的因子 a，b = x / a 一定满足 b >= a。
    for (ll a = 1; a * a <= x; a++) {
        if (x % a != 0) {
            continue;
        }
        ll b = x / a;
        if ((a + b) % 2 == 0) {
            return true; // a、b 同奇偶，可以还原出整数 y、z
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll L, R;
    cin >> L >> R;

    ll ans = 0;
    // 朴素做法：区间里每个数都单独判断一次。
    for (ll x = L; x <= R; x++) {
        if (can_represent(x)) {
            ans++;
        }
    }

    cout << ans << '\n';

    return 0;
}

复杂度

逐个判断 $x$ 需要 $O(\sqrt{x})$，区间里共有 $R-L+1$ 个数，总复杂度 $O\big((R-L+1)\sqrt{R}\big)$。

瓶颈

暴力解本身完全正确，但它有两个致命问题：

1. $R$ 可以到 $10^9$，光是区间长度就可能达到 $10^9$，逐个数枚举已经不可能。
2. 即使只处理一个数，$O(\sqrt{x})$ 也意味着约 $3\times 10^4$ 次循环，乘上区间长度后彻底超时。

所以要拿满分，必须找出「哪些数可行」的充要条件，然后不再逐个判断。

正解

思路

回到暴力的判据：$x = ab$ 且 $a,b$ 同奇偶。把「同奇偶」按两种情形展开就能看出规律。

设有因子对 $a\cdot b = x$，且 $a,b$ 同奇偶：

• 都是奇数：奇数乘奇数还是奇数，所以 $x$ 是奇数；
• 都是偶数：写 $a = 2a',\ b = 2b'$，则 $x = 4a'b'$，所以 $x$ 是 $4$ 的倍数。

反过来看，两种情形都真的能构造出来：

• $x$ 是奇数时，取 $a = 1,\ b = x$，两个因子都是奇数，$y = \dfrac{x+1}{2},\ z = \dfrac{x-1}{2}$ 是整数。例如 $5 = 3^2 - 2^2$。
• $x$ 是 $4$ 的倍数时，$x/2$ 是偶数，取 $a = 2,\ b = x/2$，两个因子都是偶数，$y = \dfrac{x+2}{4},\ z = \dfrac{x-2}{4}$ 是整数。例如 $4 = 2^2 - 0^2$，$8 = 3^2 - 1^2$。

至于一个奇数一个偶数的情况，$a+b$ 是奇数，$y$ 不是整数，永远不可行。

于是得到本题最关键的一句话：

$x$ 可以表示为两个整数平方之差，当且仅当 $x$ 是奇数或者 $4$ 的倍数。

用模运算写就是 $x \equiv 1,3 \pmod 2$ 或 $x \equiv 0 \pmod 4$；等价地说，偶数中只有 $4$ 的倍数可行，$x \equiv 2 \pmod 4$ 的数（$2,6,10,\dots$）全部不行。

接下来只是计数问题。由于「奇数」和「$4$ 的倍数」这两类互不相交（$4$ 的倍数都是偶数，不可能是奇数），可以在 $[1,n]$ 里直接相加：

答案就是前缀相减：

例如 $L=1,R=5$：奇数有 $1,3,5$ 共 $3$ 个，$4$ 的倍数有 $4$ 共 $1$ 个，$F(5)=4$；$F(0)=0$，所以答案是 $4$，与样例一致。

边界上注意 $F(0)$ 表示「$[1,0]$ 中可行数的个数」，应当是 $0$，代码里对 $n \leqslant 0$ 直接返回 $0$ 就稳了。题面保证 $L \geqslant 1$，因此 $L-1 \geqslant 0$，不会出现负数下取整的问题；不过把 $n \leqslant 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
34
35
36
37
38/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-03 10:37
 * update_at: 2026-10-03 10:37
 */
// P9231 [蓝桥杯 2023 省 A] 平方差
// 核心结论：x 能写成 x = y^2 - z^2 当且仅当 x 是奇数或者 4 的倍数。
// 于是答案 = [1,R] 中这类数的个数 减去 [1,L-1] 中这类数的个数。
#include <iostream>
using namespace std;

typedef long long ll;

// 统计 [1,n] 中“奇数或 4 的倍数”的个数。
// 一个数不可能同时是奇数和 4 的倍数，所以两类直接相加，不会重复计算。
ll prefix_count(ll n) {
    if (n <= 0) {
        return 0;
    }
    ll odd = (n + 1) / 2; // 1,3,5,... 的个数
    ll mul4 = n / 4;      // 4,8,12,... 的个数
    return odd + mul4;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll L, R;
    cin >> L >> R;

    // 前缀和思想：区间答案 = F(R) - F(L-1)。
    cout << prefix_count(R) - prefix_count(L - 1) << '\n';

    return 0;
}

复杂度

每个 $F(n)$ 只有两次除法和一次加法，答案需要算两次 $F$，所以时间复杂度是 $O(1)$，空间复杂度 $O(1)$。

由于 $R \leqslant 10^9$，答案最大不超过 $7.5\times 10^8$，而中间量 $R$ 与 $R+1$ 都在 $10^9$ 量级，32 位 int 其实也不会溢出；但习惯上仍然使用 long long，避免以后改动代码时踩坑。

总结

这道题的推导链条非常短，值得完整记住：

1. 用平方差公式分解：$x = y^2 - z^2 = (y-z)(y+z)$；
2. 于是 $x$ 可行等价于「存在同奇偶的因子对」，即 $x$ 是奇数或 $4$ 的倍数；
3. 奇数与 $4$ 的倍数互不重叠，用前缀计数 $F(R)-F(L-1)$ 一次算出答案。

最容易踩的坑是把条件记成「偶数都行」：真正的偶数是 $4$ 的倍数，$2,6,10,\dots$ 这类模 $4$ 余 $2$ 的数永远写不成平方差。写代码时再注意两件事：区间用前缀相减而不是直接枚举，以及把 $n \leqslant 0$ 的情况单独返回 $0$。