POJ - 1840 - Eqs = map / 哈希 + map

http://poj.org/problem?id=1840

题意：求 \(a_1x_1^3+a_2x_2^3+a_3x_3^3+a_4x_4^3+a_5x_5^3=0\) 的整数解，其中所有变量的取值都是 \([-50,50]\) ，且 \(x_i \neq 0\)

暴力枚举，但是要怎么分两半呢？事实证明是前半部分分2个，后半部分分3个会更好，为什么呢？

大概是多了一个 \(\log_{2}{100}\)吧，也是差不多7倍常数了。

前半部分分两个是：
\(O(n^2\log(n^2)+n^3\log(n^2))\)

前半部分分三个就白白多了7倍常数，实属逗比。

可惜POJ用不了unordered_map，待会手写一发hash看看？

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

map<int, int> M;

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    int a1, a2, a3, a4, a5;
    scanf("%d%d%d%d%d", &a1, &a2, &a3, &a4, &a5);
    for(int x1 = -50; x1 <= 50; ++x1) {
        if(x1 == 0)
            continue;
        int p1 = a1 * x1 * x1 * x1;
        for(int x2 = -50; x2 <= 50; ++x2) {
            if(x2 == 0)
                continue;
            int p2 = a2 * x2 * x2 * x2;
            M[p1 + p2]++;
        }
    }
    ll ans = 0;
    for(int x3 = -50; x3 <= 50; ++x3) {
        if(x3 == 0)
            continue;
        int p3 = a3 * x3 * x3 * x3;
        for(int x4 = -50; x4 <= 50; ++x4) {
            if(x4 == 0)
                continue;
            int p4 = a4 * x4 * x4 * x4;
            for(int x5 = -50; x5 <= 50; ++x5) {
                if(x5 == 0)
                    continue;
                int p5 = a5 * x5 * x5 * x5;
                map<int, int>::iterator it = M.find(-p3 - p4 - p5);
                if(it != M.end())
                    ans += it->second;
            }
        }
    }
    printf("%lld\n", ans);
}

一个假的哈希，大概就是把它按余数分裂成几棵平衡树来减小树的规模，大概取值合理的话可以快3倍左右（原本平衡树应该是 \(\log_2{10^6}=20\) 的，套个余数哈希（余数为 \(5\times10^4\) ）就快了三倍，大概符合 \(\log_2{10^2}=7\) ），注意初始化map是需要时间的，所以并不是余数取越大越好，而且的确会创建map的实例，占用内存空间。

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

const int MAXN = 49999;
struct HashTable {
    map<int, int> M[MAXN];
    void insert(int x) {
        int p = x % MAXN;
        if(p < 0)
            p += MAXN;
        M[p][x]++;
    }
    int count(int x) {
        int p = x % MAXN;
        if(p < 0)
            p += MAXN;
        map<int, int>::iterator it = M[p].find(x);
        if(it != M[p].end())
            return it->second;
        return 0;
    }
} ht;

//寻找n以内的一个最大的质数
/*const int MAXP=2e6;
bool np[MAXP+1];
void find_p(int n){
    np[1]=1;
    for(int i=1;i<=n;++i){
        if(np[i])
            continue;
        for(int j=i+i;j<=n;j+=i)
            np[j]=1;
    }
    for(int i=n;;--i){
        if(!np[i]){
            printf("MAXP=%d\n",i);
            break;
        }
    }
}*/

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    //find_p(5e4);
    int a1, a2, a3, a4, a5;
    scanf("%d%d%d%d%d", &a1, &a2, &a3, &a4, &a5);
    for(int x1 = -50; x1 <= 50; ++x1) {
        if(x1 == 0)
            continue;
        int p1 = a1 * x1 * x1 * x1;
        for(int x2 = -50; x2 <= 50; ++x2) {
            if(x2 == 0)
                continue;
            int p2 = a2 * x2 * x2 * x2;
            ht.insert(p1 + p2);
        }
    }
    ll ans = 0;
    for(int x3 = -50; x3 <= 50; ++x3) {
        if(x3 == 0)
            continue;
        int p3 = a3 * x3 * x3 * x3;
        for(int x4 = -50; x4 <= 50; ++x4) {
            if(x4 == 0)
                continue;
            int p4 = a4 * x4 * x4 * x4;
            for(int x5 = -50; x5 <= 50; ++x5) {
                if(x5 == 0)
                    continue;
                int p5 = a5 * x5 * x5 * x5;
                ans += ht.count(-p3 - p4 - p5);
            }
        }
    }
    printf("%lld\n", ans);
}

但是假如哈希套哈希再套平衡树说不定会快到飞起？

POJ - 1840 - Eqs = map / 哈希 + map

原文：https://www.cnblogs.com/Inko/p/11729194.html