题解

这道题目要求我们找出满足如下方程的所有解：

$$a_1 x_1^3 + a_2 x_2^3 + a_3 x_3^3 + a_4 x_4^3 + a_5 x_5^3 = 0 $$

其中，$x_1, x_2, x_3, x_4, x_5$ 是在区间 $[-50, 50]$ 内的整数，且 $x_i \neq 0$ （即 $x_1, x_2, x_3, x_4, x_5$ 都不能为零）。我们需要计算出满足该方程的所有解的数量。

解题思路

1. 方程的分析：

   • 这个方程涉及到五个变量 $x_1, x_2, x_3, x_4, x_5$，每个变量的取值范围是 $[-50, 50]$，且每个变量不能为零。
   • 方程的左边是五个项的加和，其中每个项是一个变量的立方乘以对应的系数。

2. 思路的优化：

   • 直接暴力枚举所有可能的组合是不可行的，因为 $x_1, x_2, x_3, x_4, x_5$ 都有 100 个可能的取值（从 $-50$ 到 $50$，去掉零）。因此，总的枚举次数是 $100^5$，这是不可接受的。

   • 我们可以利用哈希表来优化搜索过程。具体来说，我们可以将方程拆分为两个部分：

     • 第一部分：$a_1 x_1^3 + a_2 x_2^3$
     • 第二部分：$a_3 x_3^3 + a_4 x_4^3 + a_5 x_5^3$

   • 我们首先计算第一部分所有可能的值并存储在哈希表中。然后，对于第二部分的每一个组合，查找其相反数是否在哈希表中，如果在，则可以组成一个有效的解。

3. 哈希表：

   • 使用哈希表 ahash 存储第一部分的结果，键是第一部分的值，值是该值出现的次数。
   • 然后，对于第二部分的每个可能值，查找其相反数在哈希表中的出现次数，累加这些次数即为解的数量。

代码实现

#include<stdio.h>
#include<string.h>

short ahash[25000005];  // 哈希表，用来存储第一部分的结果

int main() {
    int a1, a2, a3, a4, a5, x1, x2, x3, x4, x5, sum, cnt;

    // 读取输入
    while (~scanf("%d%d%d%d%d", &a1, &a2, &a3, &a4, &a5)) {
        memset(ahash, 0, sizeof(ahash));  // 清空哈希表
        
        // 计算第一部分的所有组合：a1*x1^3 + a2*x2^3
        for (x1 = -50; x1 <= 50; x1++) {
            if (!x1) continue;  // 忽略 x1 = 0
            for (x2 = -50; x2 <= 50; x2++) {
                if (!x2) continue;  // 忽略 x2 = 0
                sum = -(a1 * x1 * x1 * x1 + a2 * x2 * x2 * x2);  // 计算第一部分的值
                if (sum < 0) sum += 25000000;  // 哈希表偏移，保证索引非负
                ahash[sum]++;  // 存储在哈希表中
            }
        }
        
        cnt = 0;
        
        // 计算第二部分的所有组合：a3*x3^3 + a4*x4^3 + a5*x5^3
        for (x3 = -50; x3 <= 50; x3++) {
            if (!x3) continue;  // 忽略 x3 = 0
            for (x4 = -50; x4 <= 50; x4++) {
                if (!x4) continue;  // 忽略 x4 = 0
                for (x5 = -50; x5 <= 50; x5++) {
                    if (!x5) continue;  // 忽略 x5 = 0
                    sum = a3 * x3 * x3 * x3 + a4 * x4 * x4 * x4 + a5 * x5 * x5 * x5;  // 计算第二部分的值
                    if (sum < 0) sum += 25000000;  // 哈希表偏移
                    cnt += ahash[sum];  // 查找相反数的出现次数
                }
            }
        }
        
        // 输出结果
        printf("%d\n", cnt);
    }
    
    return 0;
}

代码解释

1. 输入读取：

   • 读取五个系数 a1, a2, a3, a4, a5，这些系数用于构建方程的左右两部分。

2. 哈希表初始化：

   • 使用 ahash 数组作为哈希表，数组的大小是 25000005，用于存储第一部分的计算结果。为了防止负值，所有的结果都加上了偏移量 25000000，确保索引为非负。

3. 第一部分计算：

   • 遍历所有可能的 x1 和 x2 值（去除零），计算并存储 -(a1*x1^3 + a2*x2^3) 的结果在哈希表中。

4. 第二部分计算：

   • 遍历所有可能的 x3, x4, x5 值（去除零），计算 a3*x3^3 + a4*x4^3 + a5*x5^3 的结果，并查找其相反数在哈希表中的出现次数。如果找到对应的相反数，累加该值。

5. 结果输出：

   • 最后输出满足方程的解的数量。

复杂度分析

• 时间复杂度：

  • 第一部分的计算时间复杂度为 $O(100 \times 100) = O(10000)$，因为 x1 和 x2 各有 100 个可能的取值。
  • 第二部分的计算时间复杂度为 $O(100 \times 100 \times 100) = O(1000000)$，因为 x3, x4, 和 x5 各有 100 个可能的取值。
  • 因此，总的时间复杂度为 $O(10000 + 1000000) = O(1000000)$，对于 $n = 16000$ 是可以接受的。

• 空间复杂度：

  • 哈希表 ahash 的空间复杂度是 $O(25000005)$，即大约 25MB，属于常数空间。

示例

输入：

37 29 41 43 47

输出：

654

结论

通过利用哈希表来存储计算的部分结果，我们有效地将问题的时间复杂度降低到了 $O(1000000)$，使得在大范围的输入下能够高效地找到解。