POJ 1840 Eqs(模拟+哈希)

冷不防 2022-06-12 05:46 145阅读 0赞

Consider equations having the following form:  
a1x1 3\+ a2x2 3\+ a3x3 3\+ a4x4 3\+ a5x5 3=0  
The coefficients are given integers from the interval \[-50,50\].  
It is consider a solution a system (x1, x2, x3, x4, x5) that verifies the equation, xi∈\[-50,50\], xi != 0, any i∈\{1,2,3,4,5\}.  
  
Determine how many solutions satisfy the given equation.

Input

The only line of input contains the 5 coefficients a1, a2, a3, a4, a5, separated by blanks.

Output

The output will contain on the first line the number of the solutions for the given equation.

Sample Input

37 29 41 43 47

Sample Output

654

题解：

比赛的时候没做出来，看到数据那么大就吓尿了，然后搜了题解就是将式子变一下形，把一部分东西移到另一边，然后就成了-（a1\*x1^3+a2\*x2^3）=a3\*x3^3+a4\*x4^3+a5\*x5^3,然后用桶排序的思想把其中一边的所有结果出现的次数记录一下，由于这里会出现负数，所以要哈希，所谓哈希我的理解就是加一个数得到另一个数使得这个数独一无二。。这个哈希数是玄学。。加小了会wa加大了爆内存，这题哈希数确定也很悬，他并没有说系数a的范围。。貌似可以理解为也是-50-+50，然后哈希数就是右边的式子范围50\*50^3\*2=12500000，由于可能是负数所以要乘2就是25000000，最后比一下结果相同就累加就是答案

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    short p[25000000];
    int main()
    {
        int a1,a2,a3,a4,a5,i,j,k,t;
        int num=0;
        memset(p,0,sizeof(p));
        scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5);
        for(i=-50;i<=50;i++)
        {
            if(i==0)
                continue;
            for(j=-50;j<=50;j++)
            {
                if(j==0)
                continue;
                int t=a1*i*i*i+a2*j*j*j;
                if(t<0)
                    t+=25000000;//哈希数
                p[t]++;
            }
        }
        for(i=-50;i<=50;i++)
        {
            if(i==0)
                continue;
            for(j=-50;j<=50;j++)
            {
                if(j==0)
                continue;
                for(k=-50;k<=50;k++)
                {
                    if(k==0)
                      continue;
                    int t=a3*i*i*i+a4*j*j*j+a5*k*k*k;
                    if(t<0)
                    t+=25000000;
                    if(p[t])//这种结果出现过
                    {
                        num+=p[t];
                    }
                }
            }
        }
        printf("%d\n",num);
    	return 0;
    }