TopCoder problem "Polynomials" used in SRM 170 (Division I Level Three)



Problem Statement

    

The theory of elliptic curves is involved with finding the number and properties of rational points -- that is, points whose x and y values are rational numbers -- and studying relationships between them. Elliptic curves, however, are curves of the form y^2 + ay + b = x^3 + cx^2 + dx + e. You feel that this type of equation is a bit too restrictive, and so you're going to generalize things a bit.

Given a String equation, and two ints xmax and ymax, find the number of lattice points (x,y) that satisfy equation and such that 0 <= x <= xmax and 0 <= y <= ymax. Lattice points are those with both coordinates being integers.

The string representing the equation follows the format "f(y)=g(x)", in more detail below:

Equation := Function(y) "=" Function(x)

Function(y) := Term(y) | Term(y) + Function(y)

Term(y) := Integer "y" Power | Integer

Integer := 0-9

Power := "^" Integer

(Function(x) is analogous to Function(y).)

If there are terms in a given function that are of the same power, consider their coefficients to be added together. For example, the equation "9y^3+5y^3=3+6" would be equivalent to "14y^3=9" (except that the latter is not in proper form and is thus illegal as input).

Note that no term of the form "Nx^0" will be allowed, to prevent ambiguity regarding 0^0.

 

Definition

    
Class:Polynomials
Method:integralPoints
Parameters:int, int, String
Returns:long
Method signature:long integralPoints(int ymax, int xmax, String equation)
(be sure your method is public)
    
 

Notes

-For C++ coders, the 64-bit integer type is long long (a gcc extension).
 

Constraints

-xmax will be between 0 and 1000000, inclusive
-ymax will be between 0 and 1000000, inclusive
-equation will be between 3 and 50 characters, inclusive
-equation will follow the form "f(y)=g(x)" given above
-no y between 0 and ymax, inclusive, will cause f(y) to exceed 2^63 - 1
-no x between 0 and xmax, inclusive, will cause g(x) to exceed 2^63 - 1
-no term of the form Nx^0 will be allowed in the input.
-no term of the form Ny^0 will be allowed in the input.
 

Examples

0)
    
5
5
"1y^1=1x^1"
Returns: 6
The points that work are those where y = x, that is, (0,0), (1,1), (2,2), (3,3), (4,4), and (5,5).
1)
    
65
34
"1y^2=1x^3"
Returns: 5
The points are (0,0), (1,1), (4,8), (9,27), and (16,64).
2)
    
1000000
1000000
"1=1x^2"
Returns: 1000001
Constants by themselves are allowed on either or both sides.
3)
    
55000
15982
"1y^4+1y^2=5+9+6"
Returns: 15983

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1852

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4655&pm=1852

Writer:

antimatter

Testers:

lbackstrom , schveiguy

Problem categories:

Search