POJ 1840-Eqs（哈希-五元方程組解的個(gè)數(shù)）

2019-11-10 17:26:34

字體：大中小

供稿：網(wǎng)友

Eqs

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 16095		Accepted: 7902

Description

Consider equations having the following form: a1x1³+ a2x2³+ a3x3³+ a4x4³+ a5x5³=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 47Sample Output
654Source
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)過(guò)這個(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*/

上一篇：codevs1215 迷宮

下一篇：Banner 淺析