Polynomials | Topcoder Archive

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

```
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).
```
65
```
```
34
```
```
"1y^2=1x^3"
```
```
Returns: 5
```
The points are (0,0), (1,1), (4,8), (9,27), and (16,64).
```
1000000
```
```
1000000
```
```
"1=1x^2"
```
```
Returns: 1000001
```
Constants by themselves are allowed on either or both sides.

"1y^4+1y^2=5+9+6"

Returns: 15983

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.