POJ 1804 Eqs

C - Eqs

Time Limit:5000MS     Memory Limit:65536KB     64bit IO Format:%I64d
& %I64u

Submit Status

Description

Consider equations having the following form:

a1x13+ a2x23+ a3x33+ a4x43+ a5x53=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
#include <iostream>
#include <cstring>
using namespace std;

#define maxn 25000005
short int hash[maxn];

int main()
{
    int a,b,c,d,e;
    while(cin>>a>>b>>c>>d>>e)
    {
        memset(hash,0,sizeof(hash));

        int i1,i2,i3,i4,i5;
        int sum=0;
        for(i1=-50;i1<=50;i1++)
        if(i1)
            for(i2=-50;i2<=50;i2++)
            if(i2)
            {
                sum=a*i1*i1*i1+b*i2*i2*i2;
                if(sum<0)
                    sum=sum+maxn;

                hash[sum]++;
            }

        int num=0;

        for(i3=-50;i3<=50;i3++)
        if(i3)
            for(i4=-50;i4<=50;i4++)
            if(i4)
                for(i5=-50;i5<=50;i5++)
                if(i5)
                {
                    sum=c*i3*i3*i3+d*i4*i4*i4+e*i5*i5*i5;
                    sum=-sum;

                    if(sum<0)
                        sum=sum+maxn;

                    if(hash[sum]!=0)
                        num=num+hash[sum];
                }

        cout<<num<<endl;
    }
    return 0;
}

POJ 1804 Eqs

时间: 08-11

POJ 1804 Eqs的相关文章

POJ 1840 Eqs(暴力)

Description Consider equations having the following form: a1x13+ a2x23+ a3x33+ a4x43+ a5x53=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,

POJ 1840 Eqs(hash)

题意  输入a1,a2,a3,a4,a5  求有多少种不同的x1,x2,x3,x4,x5序列使得等式成立   a,x取值在-50到50之间 直接暴力的话肯定会超时的   100的五次方  10e了都    然后可以考虑将等式变一下形   把a1*x1^3+a2*x2^3移到右边   也就是-(a1*x1^3+a2^x2^3)=a3*x3^3+a4*x4^3+a5*x5^3 考虑到a1*x1^3+a2^x2^3的最大值50*50^3+50*50^3=12500000  这个数并不大  可以开这么大

归并排序求逆序数(POJ 1804,POJ 2299,HDU 4911)

首先,明确两个概念: 逆序对:数列a[1],a[2],a[3]-中的任意两个数a[i],a[j] (i<j),如果a[i]>a[j],那么我们就说这两个数构成了一个逆序对. 逆序数:一个数列中逆序对的总数. 例题一:POJ 1804.   点击打开链接 解题思路:每次交换只能减少一个逆序,而且必定能减少一个逆序,从而问题就转换为求逆序个数了.这题数据规模很小,暴力可过. 我这里提供了用Merge_sort的方法求解逆序数,时间复杂度为O(nlogn). 关于归并排序:归并排序是将数列a[l,h

POJ 1840 Eqs(哈希)

题目地址:POJ 1840 sad...整个比赛期间一直以为是用什么定理或数学公式推导来做..一直没仔细看..结果最后5分钟的时候才看到每个元素的数据范围只是[-50,50]...算了..就算看到了也做不出来..因为会MLE,解决MLE需要把hash数组的定义类型定义成short...这我是不可能想出来的....也没遗憾了.. 这题就是先求前两个for循环,将结果用hash数组存起来.再进行后面三个for循环,如果值为相反数的话,说明和为0.然后记录有多少个. 代码如下: #include <i

POJ 1840.Eqs

Eqs Time Limit:5000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u Submit Status Practice POJ 1840 Description Consider equations having the following form: a1x1 3+ a2x2 3+ a3x3 3+ a4x4 3+ a5x5 3=0 The coefficients are given integers fr

POJ 1804 Brainman(5种解法,好题,【暴力】,【归并排序】,【线段树单点更新】,【树状数组】,【平衡树】)

Brainman Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 10575   Accepted: 5489 Description BackgroundRaymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just b

POJ 1804

题目:http://poj.org/problem?id=1804 大意:给你一串数字,排序.求出最少的交换次数  \ 我用归并做的 #include<iostream> #include<cstring> using namespace std; int aa[500010],bb[500010]; long long s=0; void merge(int l,int m,int r) { int i=l,j=m+1,t=0; while(i<=m&&j&

poj 1840 Eqs 【解五元方程+分治+枚举打表+二分查找所有key 】

Eqs Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 13955   Accepted: 6851 Description Consider equations having the following form: a1x13+ a2x23+ a3x33+ a4x43+ a5x53=0 The coefficients are given integers from the interval [-50,50]. It i

poj 1840 Eqs (Hash)

/* 这题10^8的暴力可以出答案 但是 慢..... 有个小小的bug 出题人卡int 却没注意short 用short可以不用hash 直接搞 49428K 313MS */ #include<iostream> #include<cstdio> #include<cstring> #define base 12500000 using namespace std; int a1,a2,a3,a4,a5,x1,x2,x3,x4,x5,ans; short f[125