题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1496
这个题目要注意剪枝，也就是如果四个系数同号，那么结果就一定是0，如过没有这个剪枝，那么很可能超时
方法一：
hash，这个方法还是比较容易想的，因为a b c d的范围和xi的范围都不大，直接hash就肯定能搞定了，这个方法比较容易实现
方法二：
二分，题目中方程式可以转换成 a b在一边，c d在一边，完成之后先处理c d，然后处理a b的时候直接在预先处理的c d中二分
查找，这个程序写袭来有很多细节，和值得优化的地方，因为数据结果 c d部分会有很多是相同的，所以在二分之前要压缩一下
但是在压缩的时候要记住没个相同的数字出现的次数，如果不这样会漏掉大量解，而且用二分也是错的，二分每次查找的是存在
还是不存在，或者说存在的位置，往往是找到一个就放手了，如果我们压缩一下就能保证每个只出现一次，那么才能保证结果正
确，而且也能减少二分次数，大概减少一次！
hash代码：
/*1496*/
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define maxn 2000000
int a,b,c,d;
int pos;
int rec[maxn*2];
int init()
{
memset(rec,0,sizeof(rec));
pos=0;
int i,j,k;
for(i=-100;i<0;i++)
{
k=-c*i*i+maxn;
for(j=-100;j<0;j++)
rec[k-d*j*j]++;
for(j=1;j<=100;j++)
rec[k-d*j*j]++;
}
for(i=1;i<=100;i++)
{
k=-c*i*i+maxn;
for(j=-100;j<0;j++)
rec[k-d*j*j]++;
for(j=1;j<=100;j++)
rec[k-d*j*j]++;
}
return 0;
}
int solve()
{
int ans=0;
int i,j,k;
for(i=-100;i<0;i++)
{
k=a*i*i+maxn;
for(j=-100;j<0;j++)
ans+=rec[k+b*j*j];
for(j=1;j<=100;j++)
ans+=rec[k+b*j*j];
}
for(i=1;i<=100;i++)
{
k=a*i*i+maxn;
for(j=-100;j<0;j++)
ans+=rec[k+b*j*j];
for(j=1;j<=100;j++)
ans+=rec[k+b*j*j];
}
return ans;
}
int main()
{
int i,j,k,num;
while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
{
if( a> 0&& b> 0&& c> 0&& d> 0|| a< 0&& b< 0&& c< 0&& d< 0 )
{
printf( "0\n" );
continue;
}
init();
k=1;
// for(i=1;i<pos;i++)
printf("%d\n",solve());
}
return 0;
}
二分代码：
/*1496*/
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define maxn 41000
int a,b,c,d;
int pos;
struct point
{
int value;
int num;
}rec[maxn];
int init()
{
pos=0;
int i,j;
for(i=-100;i<0;i++)
{
for(j=-100;j<0;j++)
rec[pos++].value=-c*i*i-d*j*j;
for(j=1;j<=100;j++)
rec[pos++].value=-c*i*i-d*j*j;
}
for(i=1;i<=100;i++)
{
for(j=-100;j<0;j++)
rec[pos++].value=-c*i*i-d*j*j;
for(j=1;j<=100;j++)
rec[pos++].value=-c*i*i-d*j*j;
}
return 0;
}
int find_ans(int num)
{
int l=0,r=pos-1,mid;
while(l<=r)
{
mid=(l+r)>>1;//printf("OK:%d %d %d\n",mid,rec[mid],num);
if(rec[mid].value==num)
return rec[mid].num;
if(rec[mid].value>num)
r=mid-1;
else
l=mid+1;
}
return 0;
}
int solve()
{
int ans=0;
int i,j;
for(i=-100;i<0;i++)
{
for(j=-100;j<0;j++)
ans+=find_ans(a*i*i+b*j*j);
for(j=1;j<=100;j++)
ans+=find_ans(a*i*i+b*j*j);
}
for(i=1;i<=100;i++)
{
for(j=-100;j<0;j++)
ans+=find_ans(a*i*i+b*j*j);
for(j=1;j<=100;j++)
ans+=find_ans(a*i*i+b*j*j);
}
return ans;
}
bool cmp(const point &a,const point &b)
{
return a.value < b.value;
}
int main()
{
int i,j,k,num;
while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
{
if( a> 0&& b> 0&& c> 0&& d> 0|| a< 0&& b< 0&& c< 0&& d< 0 )
{
printf("0\n" );
continue;
}
init();
sort(rec,rec+pos,cmp);
k=1;
rec[0].num=1;
for(i=1;i<pos;i++)
if(rec[i].value!=rec[i-1].value)
{
rec[k]=rec[i];
rec[k].num=1;
k++;
}
else
{
rec[k-1].num++;
}
pos=k;
printf("%d\n",solve());
}
return 0;
}