poj 1840 hashマッピング
1416 ワード
注意short hash[250001];intでタイムアウト
暴力解決....式は変形し,hashマッピングを用いて多対一である.
暴力解決....式は変形し,hashマッピングを用いて多対一である.
#include<stdio.h>
#include<string.h>
#define max 25000000
short hash[25000001];// a,x1,b,x2 (50*50^3*2)*2
int main()
{
int a,b,c,d,e;
int x1,x2,x3,x4,x5;
int res;
while(scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)==5)
{
memset(hash,0,sizeof(hash));
for(x1=-50; x1<=50; x1++)
{
if(x1==0)
continue;
for(x2=-50; x2<=50; x2++)
{
if(x2==0)
continue;
res=(a*x1*x1*x1+b*x2*x2*x2)*(-1);
if(res<0)
res+=max;
hash[res]++;
}
}
int ans=0;
for(x3=-50; x3<=50; x3++)
{
if(x3==0)
continue;
for(x4=-50; x4<=50; x4++)
{
if(x4==0)
continue;
for(x5=-50; x5<=50; x5++)
{
if(x5==0)
continue;
res=x3*x3*x3*c+x4*x4*x4*d+x5*x5*x5*e;
if(res<0)
res+=max;
ans+=hash[res];
}
}
}
printf("%d
",ans);
}
return 0;
}