poj 1840 hashマッピング

1416 ワード

注意short hash[250001];intでタイムアウト
暴力解決....式は変形し,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; }