POJ 1840 HASH

题目链接：http://poj.org/problem?id=1840

题意：公式a1x1^3+ a2x2^3+ a3x3^3+ a4x4^3+ a5x5^3=0,现在给定a1~a5，求有多少个(x1~x5)的组合使得公式成立。并且(x1~x5)取值再[-50,50]且不能为0

思路：因为x的值范围比较小，只有100.所以可以先求出 a1x1^3+a2x2^3+a3x3^3. 然后在求 (-1)*(a4x4^3+a5x5^3)从前面的所得的Hash表进行二分查找。

#include<iostream>

#include<algorithm>

#include<cstring>

#include<string>

#include<cstdio>

#include<vector>

#include<cmath>

#include<time.h>

#include<map>

using namespace std;

typedef long long int LL;

const int MAXN=+;//100^3

int a,b,c,d,e;

int Hash[MAXN];

int main(){

#ifdef kirito

    freopen("in.txt","r",stdin);

    freopen("out.txt","w",stdout);

#endif

    int start=clock();

    while(~scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)){

        int cnt=,ans=;

        for(int i=-;i<=;i++){ //make a1x1^3+a2x2^3+a3x3^3

            if(i==){continue;}

            for(int j=-;j<=;j++){

                if(j==){continue;}

                for(int k=-;k<=;k++){

                    if(k==){continue;}

                    int Sum=a*i*i*i+b*j*j*j+c*k*k*k;

                    Hash[cnt++]=Sum;

                }

            }

        }

        sort(Hash,Hash+cnt); //sorted

        for(int i=-;i<=;i++){ //make  (-1)*(a4x4^3+a5x5^3)

            if(i==){continue;};

            for(int j=-;j<=;j++){

                if(j==){continue;}

                int Sum=(-)*(d*i*i*i+e*j*j*j);//the search number

                for(int k=lower_bound(Hash,Hash+cnt,Sum)-Hash;k<cnt;k++){//binary search the number

                    if(Hash[k]!=Sum){

                        break;

                    }

                    else{

                        ans++;

                    }

                }

            }

        }

        printf("%d\n",ans);

    }

#ifdef LOCAL_TIME

    cout << "[Finished in " << clock() - start << " ms]" << endl;

#endif

    return ;

}