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    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include //形如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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include //形如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;
}