POJ 1840-Eqs（哈希-五元方程组解的个数）

心已赠人 2022-07-12 03:39 140阅读 0赞

Eqs

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;5000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;16095</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;7902</td> 
  </tr> 
 </tbody> 
</table>

Description

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

Source

[Romania OI 2002][]

## 题目意思： ##

有一个五元一次方程，给出五个系数，解的范围是\[-50,0)(0,50\]，求解的个数。

## 解题思路： ##

直接五层for循环肯定就爆了，所以原式变形成：-(a1x1^3+ a2x2^3)=a3x3^3+ a4x4^3+ a5x5^3=0。

哈希数组的下标表示求出的数，数组的值表示这个数出现的次数（类似于桶排序的思想）。

①先求出等式左边的值，将对应下标哈希数组的值加1，因为2\*50\*50^3=12500000，所以正负加起来最多有12500000\*2=25000000种不同的值。

注意这个值可能为负，所以负数时要将其加上25000000再进行处理。

②然后枚举出等式右边的值，判断是否在出现过这个值，然后利用哈希数组将解的个数加上这个数出现的次数。

同样地这个值可能为负，所以负数时要将其加上25000000再进行处理。

#include<iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    /*a1x13+ a2x23+ a3x33+ a4x43+ a5x53=0*/
    short ha[25000000];//左半部分的值
    int main()
    {
    #ifdef ONLINE_iUDGE
    #else
        //freopen("F:/cb/read.txt","r",stdin);
        //freopen("F:/cb/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        memset(ha,0,sizeof(ha));
        int a1,a2,a3,a4,a5;  //系数
        while(cin>>a1>>a2>>a3>>a4>>a5)
        {
            int a,b,c,d,e,ans=0;
            for(a=-50; a<=50; ++a)
                for(b=-50; b<=50; ++b)
                    if(a!=0&&b!=0)
                    {
                        int t=a*a*a*a1+b*b*b*a2;
                        t=-t;
                        if(t<0) t+=25000000;//负值
                        ++ha[t];
                    }
            for(c=-50; c<=50; ++c)
                for(d=-50; d<=50; ++d)
                    for(e=-50; e<=50; ++e)
                        if(c!=0&&d!=0&&e!=0)
                        {
                            int num=c*c*c*a3+d*d*d*a4+e*e*e*a5;
                            if(num<0) num+=25000000;
                            ans+=ha[num];
                        }
            cout<<ans<<endl;
        }
        return 0;
    }
    /*
    37 29 41 43 47
    */

[Romania OI 2002]: http://poj.org/searchproblem?field=source&key=Romania+OI+2002