POJ1840

Written by    23:02 December 20, 2014 

POJ1840

Eqs
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 14507 Accepted: 7122

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

Sample Output

Source

首先要肯定是不能直接暴力的, 把五组数字分成两拨,一拨三个,一拨两个,前一拨o(100^3)打表,离散化后,对第二拨处理,从表中二分查找值,总共O(100^3+100^2*log(100^3)), 这样的话可以AC, 但是还也可以用Hash表优化, 优化过后速度可以提高一个数量级.

代码最优化原则: 只留下最高效的代码.

Category : acmstudy

Tags :