题解

问题分析

题目要求统计满足条件的平方数对 $(x^2, y^2)$ 的数量，其中：

• $l \le y^2 < x^2 \le r$
• $x^2 - y^2 = d$

关键公式变换

利用平方差公式：

设：

• $a = x - y$
• $b = x + y$

则有：

• $a \times b = d$
• $x = \frac{a + b}{2}$
• $y = \frac{b - a}{2}$

约束条件

1. $a, b$ 必须是正整数且 $a < b$（因为 $x > y > 0$）
2. $a$ 和 $b$ 必须同奇偶性（否则 $x, y$ 不是整数）
3. $l \le y^2 < x^2 \le r$

算法思路

枚举因子法：

1. 枚举所有因子对：

   • 遍历 $a$ 从 $1$ 到 $\sqrt{d}$
   • 如果 $a$ 能整除 $d$，则 $b = d / a$
   • 确保 $a < b$

2. 检查奇偶性：

   • 如果 $(a - b)$ 是偶数，则 $x, y$ 是整数

3. 计算平方值并检查范围：

   • $x = \frac{a + b}{2}$，$y = \frac{b - a}{2}$
   • 验证 $l \le y^2$ 且 $x^2 \le r$

复杂度分析

• 时间复杂度：$O(\sqrt{d})$，只需枚举到 $\sqrt{d}$
• 空间复杂度：$O(1)$，只使用常数空间

算法步骤

1. 读入 $d, l, r$
2. 初始化答案 $ans = 0$
3. 遍历 $a$ 从 $1$ 到 $\sqrt{d}$：
   • 如果 $d \% a == 0$：
     • 令 $b = d / a$
     • 如果 $(a - b) \% 2 == 0$：
       • 计算 $x = (a + b) / 2$，$y = (b - a) / 2$
       • 如果 $l \le y^2$ 且 $x^2 \le r$，则 $ans$++
4. 输出 $ans$

样例验证

样例1：$d=64$

• 因子对 $(2,32)$：$x=17, y=15$ → $289,225$（超出范围）
• 因子对 $(4,16)$：$x=10, y=6$ → $100,36$（符合条件）
• 答案：1

样例2：$d=64$

• $(4,16)$：$100,36$（符合）
• $(8,8)$：$x=8,y=0$（$y$ 不是自然数）
• 其他因子对都不满足条件
• 答案：1（与样例输出2不符，说明代码可能有误）

算法标签

• 数论
• 因子枚举
• 平方差公式
• 数学推导

注意：根据样例2，代码逻辑似乎有问题，可能漏掉了某些情况。