poj 1840 Eqs

Eqs Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 15314 Accepted: 7518 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

提示

題意：

我們給出一個方程：

a1x1^3+a2x2^3+a3x3^3+a4x4^3+a5x5^3=0。（-50<=ai<=50，-50<=xi<0∪0<xi<=50）

求有幾種情況滿足方程？

思路：

a1x1^3+a2x2^3=-（a3x3^3+a4x4^3+a5x5^3）。

先以a1x1^3+a2x2^3的所有值全部打表，注意是全部，50^4+50^4=12500000,連上負數是25000000，并且我們記錄的是這個值産生的次數而不是存不存在。

之後用-（a3x3^3+a4x4^3+a5x5^3）去做比較，相同就加。

示例程式

Source Code

Problem: 1840		Code Length: 1147B
Memory: 49356K		Time: 516MS
Language: GCC		Result: Accepted
#include <stdio.h>
#include <string.h>
short a[25000001];
int main()
{
    int a1,a2,a3,a4,a5,x1,x2,x3,x4,x5,y,num=0;
    memset(a,0,sizeof(a));
    scanf("%d %d %d %d %d",&a1,&a2,&a3,&a4,&a5);
    for(x1=-50;x1<=50;x1++)
    {
        if(x1==0)
        {
            x1++;
        }
        for(x2=-50;x2<=50;x2++)
        {
            if(x2==0)
            {
                x2++;
            }
            y=a1*x1*x1*x1+a2*x2*x2*x2;
            if(y<0)
            {
                y=y+25000000;			//大于12500000的就是負數了，這裡是為了數組下标好做統計
            }
            a[y]++;
        }
    }
    for(x3=-50;x3<=50;x3++)
    {
        if(x3==0)
        {
            x3++;
        }
        for(x4=-50;x4<=50;x4++)
        {
            if(x4==0)
            {
                x4++;
            }
            for(x5=-50;x5<=50;x5++)
            {
                if(x5==0)
                {
                    x5++;
                }
                y=(-1)*(a3*x3*x3*x3+a4*x4*x4*x4+a5*x5*x5*x5);
                if(y<0)				//同理
                {
                    y=y+25000000;
                }
                num=num+a[y];
            }
        }
    }
    printf("%d",num);
    return 0;
}