Description

Input

Output

Sample Input

37 29 41 43 47
Sample Output
654
Source
Romania OI 2002
題目意思：
有一個(gè)五元一次方程，給出五個(gè)系數(shù)，解的范圍是[-50,0)(0,50]，求解的個(gè)數(shù)。
解題思路：
直接五層for循環(huán)肯定就爆了，所以原式變形成：-(a1x1^3+ a2x2^3)=a3x3^3+ a4x4^3+ a5x5^3=0。哈希數(shù)組的下標(biāo)表示求出的數(shù)，數(shù)組的值表示這個(gè)數(shù)出現(xiàn)的次數(shù)（類似于桶排序的思想）。①先求出等式左邊的值，將對(duì)應(yīng)下標(biāo)哈希數(shù)組的值加1，因?yàn)?*50*50^4=25000000，所以最多有25000000種不同的值。注意這個(gè)值可能為負(fù)，所以負(fù)數(shù)時(shí)要將其加上25000000再進(jìn)行處理。②然后枚舉出等式右邊的值，判斷是否在出現(xiàn)過這個(gè)值，然后利用哈希數(shù)組將解的個(gè)數(shù)加上這個(gè)數(shù)出現(xiàn)的次數(shù)。同樣地這個(gè)值可能為負(fù)，所以負(fù)數(shù)時(shí)要將其加上25000000再進(jìn)行處理。
#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;  //系數(shù)    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;//負(fù)值                    ++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*/