题目解析

该题目要求计算满足条件的鱼缸数量。鱼缸的底面为 (a \times b)，高为 (h)，且对角线长度 (\sqrt{a^2 + b^2 + h^2}) 必须为整数，且不超过 (n)。两个鱼缸不同当且仅当高度不同或底面无序对 ({a, b}) 不同。代码通过预计算和组合计数来高效解决这个问题。

算法思路

1. 预计算底面平方和：
   遍历所有可能的底面边长 (a) 和 (b)（其中 (a \geq b)，确保底面无序对不重复），计算 (a^2 + b^2) 的值，并统计每个值出现的次数。这里使用数组 f 存储，f[x] 表示 (x = a^2 + b^2) 的底面无序对数量。

2. 枚举对角线长度和高度：
   遍历所有可能的对角线长度 (l)（从 1 到 (n)）和高度 (h)（从 1 到 (l-1)）。对于每个 ((l, h))，计算 (l^2 - h^2)，即所需的 (a^2 + b^2) 值。如果该值在预计算中存在（即 f[l^2 - h^2] > 0），则将这些底面与高度 (h) 组合形成的鱼缸数量累加到答案中。

代码步骤详解

• 初始化：
  读取整数 (n)，创建数组 f 大小为 (n \times n)，用于存储底面平方和的计数。

• 预计算底面平方和：
  使用两层循环遍历 (a) 和 (b)（(b \leq a)），确保 (a^2 + b^2 < n^2)（因为对角线 (l \leq n)，所以 (l^2 \leq n^2)）。对于每个有效的 ((a, b))，增加 f[a*a + b*b] 的计数。

• 统计鱼缸数量：
  遍历对角线长度 (l)（从 1 到 (n)）和高度 (h)（从 1 到 (l-1)）。计算 (l^2 - h^2)，并累加 f[l*l - h*h] 到答案中。这表示对于固定 (l) 和 (h)，所有满足 (a^2 + b^2 = l^2 - h^2) 的底面无序对都可以与高度 (h) 组合形成一个鱼缸。

• 输出结果：
  打印满足条件的鱼缸总数。

时间复杂度

• 预计算部分循环次数约为 (O(n^2))，因为 (a) 和 (b) 最多遍历到 (n)。
• 统计部分循环次数也为 (O(n^2))，因为 (l) 和 (h) 最多遍历到 (n)。
• 总体时间复杂度为 (O(n^2))，在 (n \leq 5000) 时可行。

示例验证

以 (n = 7) 为例，代码计算得到 7 个鱼缸，与样例输出一致。具体鱼缸对应关系如下：

• (l=3)：底面 ({1,2}) 高 2 和底面 ({2,2}) 高 1。
• (l=6)：底面 ({2,4}) 高 4 和底面 ({4,4}) 高 2。
• (l=7)：底面 ({2,3}) 高 6、底面 ({2,6}) 高 3 和底面 ({3,6}) 高 2。

该算法通过预计算和组合枚举，高效地统计了所有满足条件的鱼缸，避免了直接三重循环的高复杂度。