本文共 2040 字，大约阅读时间需要 6 分钟。
要解决这个问题，我们需要找到满足特定二次方程的所有整数解的数量。方程的形式为 (a \cdot x1^2 + b \cdot x2^2 + c \cdot x3^2 + d \cdot x4^2 = 0)，其中 (a, b, c, d) 是非零的整数，范围在 ([-50, 50]) 之间。(x1, x2, x3, x4) 也是非零的整数，范围在 ([-100, 100]) 之间。
方法思路
为了高效地解决这个问题，我们可以采用以下步骤：
预处理平方值：由于 (x1, x2, x3, x4) 的取值范围是对称的，我们可以预先生成所有可能的平方值，并将它们存储在哈希表中，以便快速查找。
处理每个测试用例：对于每个给定的 (a, b, c, d)，我们需要计算左边 (a \cdot x1^2) 的值，并在哈希表中查找是否存在一个组合，使得 (b \cdot x2^2 + c \cdot x3^2 + d \cdot x4^2) 等于负的左边值。
统计满足条件的解的数量：通过遍历所有可能的 (x1, x2, x3, x4) 组合，计算各自的平方项，并根据系数相乘后的结果是否相等来判断是否满足方程。
这种方法利用哈希表预处理可能的平方值，快速查找满足条件的组合，从而在合理的时间内处理大量的测试用例。
代码实现
#include #include #include #include using namespace std;int main(int argc, char **argv) { const int maxn = 1e6 + 7; unordered_map hash1, hash2; while (~scanf("%d %d %d %d", &a, &b, &c, &d)) { if ((a > 0 && b > 0 && c > 0 && d > 0) || (a < 0 && b < 0 && c < 0 && d < 0)) { printf("0\n"); continue; } int ans = 0; // 预处理x1和x2的平方 for (int i = 1; i <= 100; ++i) { for (int j = 1; j <= 100; ++j) { int x = a * i * i + b * j * j; if (x > 0) { hash1[x]++; } else { hash2[-x]++; } } } // 遍历x3和x4，计算c和d的部分 for (int i = 1; i <= 100; ++i) { for (int j = 1; j <= 100; ++j) { int x = c * i * i + d * j * j; if (x > 0) { ans += hash2[x]; } else { ans += hash1[-x]; } } } printf("%d\n", ans); } return 0;}
代码解释
预处理平方值：我们使用两个哈希表 hash1 和 hash2 来分别存储正数和负数的平方和。通过遍历 (x1) 和 (x2) 的所有可能值，计算它们的平方和，并将结果存储在哈希表中。
处理每个测试用例：对于每个给定的 (a, b, c, d)，我们计算左边 (a \cdot x1^2 + b \cdot x2^2) 的值。根据这个值，我们在哈希表中查找右边 (c \cdot x3^2 + d \cdot x4^2) 是否等于负的左边值。如果找到匹配项，计数器 ans 就会增加相应的次数。
输出结果：对于每个测试用例，输出满足条件的解的数量。
这种方法通过预处理和哈希查找，有效地减少了计算量，使得我们能够在合理的时间内处理大量的测试用例。
转载地址：http://msfmz.baihongyu.com/