本文共 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;}
     
    
   

二分解方程

二分解方程是一种基于排序和二分查找的方法，通过将问题转化为查找满足条件的数对来解决。这种方法的时间复杂度较高，但对于复杂的查询条件非常有效。

#include 
   
    using 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/