hdu 1496 Equations （雙重循環+hash查找）

一個四元二次方程，給出因子a,b,c,d，xi在【-100,100】之間但不等於零。求方程等於零時有多少種解。

題目可以暴搞....但總是不和諧的。

將a*x1*x1+b*x2*x2的的可能值枚舉出來hash一下，然後c*x3*x3+d*x4*x4用hash來查找，計數值乘以16就行了（xi可正可負）

處理沖突後，hash數組可以小很多，因為雙重100的循環，最多只有10000個不同的答案。

#include <iostream>   
#include <algorithm>   
#include <cmath>   
#include <cstdio>   
#include <cstdlib>   
#include <cstring>   
#include <string>   
#include <vector>   
#include <set>   
#include <queue>   
#include <stack>   
#include <climits>//形如INT_MAX一類的   
#define MAX 50050   
#define INF 0x7FFFFFFF   
#define REP(i,s,t) for(int i=(s);i<=(t);++i)   
#define ll long long   
#define mem(a,b) memset(a,b,sizeof(a))   
#define mp(a,b) make_pair(a,b)   
# define eps 1e-5   
//#pragma comment(linker, "/STACK:36777216") ///傳說中的外掛   
using namespace std;  
  
int hash[MAX],cnt[MAX];  
  
int HASH(int key)//處理沖突   
{  
    int t = key % MAX;  
    if(t < 0)  
        t += MAX;  
    while(hash[t] != key && cnt[t] != 0)  
    {  
        t = (t+1) % MAX;  
    }  
    return t;  
}  
  
int main()  
{  
    int a,b,c,d;  
    while(scanf("%d%d%d%d",&a,&b,&c,&d) != EOF)  
    {  
        mem(hash,0);  
        mem(cnt,0);  
        if((a>0 && b>0 && c>0 && d>0 )|| (a<0 && b<0 && c<0 && d<0) )  
        {  
            printf("0\n");  
            continue;  
        }  
        REP(i,1,100)  
        {  
            REP(j,1,100)  
            {  
                int sum = a*i*i + b*j*j;  
                int tmp = HASH(sum);  
                hash[tmp] = sum;  
                cnt[tmp]++;  
            }  
        }  
        int ans = 0;  
        REP(i,1,100)  
        {  
            REP(j,1,100)  
            {  
                int sum = c*i*i + d*j*j;  
                int tmp = HASH(-sum);  
                ans += cnt[tmp];  
            }  
        }  
        printf("%d\n",ans * 16);  
    }  
    return 0;  
}  

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一類的
#define MAX 50050
#define INF 0x7FFFFFFF
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///傳說中的外掛
using namespace std;

int hash[MAX],cnt[MAX];

int HASH(int key)//處理沖突
{
    int t = key % MAX;
    if(t < 0)
        t += MAX;
    while(hash[t] != key && cnt[t] != 0)
    {
        t = (t+1) % MAX;
    }
    return t;
}

int main()
{
    int a,b,c,d;
    while(scanf("%d%d%d%d",&a,&b,&c,&d) != EOF)
    {
        mem(hash,0);
        mem(cnt,0);
        if((a>0 && b>0 && c>0 && d>0 )|| (a<0 && b<0 && c<0 && d<0) )
        {
            printf("0\n");
            continue;
        }
        REP(i,1,100)
        {
            REP(j,1,100)
            {
                int sum = a*i*i + b*j*j;
                int tmp = HASH(sum);
                hash[tmp] = sum;
                cnt[tmp]++;
            }
        }
        int ans = 0;
        REP(i,1,100)
        {
            REP(j,1,100)
            {
                int sum = c*i*i + d*j*j;
                int tmp = HASH(-sum);
                ans += cnt[tmp];
            }
        }
        printf("%d\n",ans * 16);
    }
    return 0;
}