Polynomials
SRM 170 · 2003-11-08 · by lbackstrom
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
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.
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.
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.
1000000 1000000 "1=1" Returns: 1000002000001
15873 918882 "0=1" Returns: 0
Submissions are judged against all 44 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Polynomials with a public method long long integralPoints(int ymax, int xmax, string equation) · 44 test cases · 2 s / 256 MB per case