本文共 2597 字，大约阅读时间需要 8 分钟。
哈希解法和二分解方程是解决某类计数问题的两种不同的方法。以下是这两种方法的实现代码以及它们的优缺点分析。
哈希解法通过预先计算所有可能的值并存储在哈希表中，然后根据需要查询哈希表来解决问题。这种方法的时间复杂度通常较低，但前提是哈希函数能够高效地进行冲突处理。
#include#include #include #define ll long longusing namespace std;const int maxn = 1e6 + 7;int hash1[maxn], hash2[maxn];int main(int argc, char** argv) { int a, b, c, d; 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; memset(hash1, 0, sizeof(hash1)); memset(hash2, 0, sizeof(hash2)); 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]++; } } 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 * 16); } return 0;}
二分解方程是一种基于排序和二分查找的方法，通过将问题转化为查找满足条件的数对来解决。这种方法的时间复杂度较高，但对于复杂的查询条件非常有效。
#includeusing namespace std;const int N = 1e5 + 9;int x[N], y[N];int a, b, c, d;int main() { 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)) { cout << "0\n"; continue; } long long ans = 0; int cnt = 0; for (int i = 1; i <= 100; ++i) { for (int j = 1; j <= 100; ++j) { x[cnt] = a * i * i + b * j * j; y[cnt++] = c * i * i + d * j * j; } } sort(x, x + cnt); sort(y, y + cnt); for (int i = 0; i < cnt; ++i) { int l = 0, r = cnt - 1; while (l < r) { int mid = (l + r) / 2; if (x[i] + y[mid] < 0) l = mid + 1; else r = mid; } long long tmp = 0; if (x[i] + y[r] == 0) { ++tmp; int k = r - 1; while (y[k] == y[r] && k >= 0) --k, ++tmp; k = r + 1; while (y[k] == y[r] && k < cnt) ++k, ++tmp; ans += tmp; while (x[i] == x[i + 1] && i + 1 < k) ans += tmp, ++i; } } printf("%lld\n", ans << 4); } return 0;}
两种方法各有优劣，选择取决于具体的应用场景和性能需求。
转载地址：http://twfm.baihongyu.com/