Statistics

Problem Statement for "Polynomials"

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

  1. 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).

  2. 65

    34

    "1y^2=1x^3"

    Returns: 5

    The points are (0,0), (1,1), (4,8), (9,27), and (16,64).

  3. 1000000

    1000000

    "1=1x^2"

    Returns: 1000001

    Constants by themselves are allowed on either or both sides.

  4. 1000000

    1000000

    "1=1"

    Returns: 1000002000001

  5. 15873

    918882

    "0=1"

    Returns: 0

  6. 55000

    15982

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

    Returns: 15983

  7. 1000000

    1000000

    "1y^2=1"

    Returns: 1000001

  8. 127

    180

    "1y^9+1y^8+1y^7+1y^6=1x^5+1x^4+1x^3+1x^2"

    Returns: 2

  9. 1000000

    1000000

    "1y^1=1x^2"

    Returns: 1001

  10. 999999

    999999

    "1y^3+2=2x^2+1"

    Returns: 2

  11. 1000000

    1000000

    "1y^3+1y^2+1y^1+8+4=1x^3+2x^2+1x^1+6+9+5"

    Returns: 0

  12. 1000000

    1000000

    "1y^2=1x^2"

    Returns: 1000001

  13. 1000000

    1000000

    "9y^2+4+9+9+9+9y^1+4y^3=9x^3+9x^2+9x^1+9"

    Returns: 0

  14. 38752

    51085

    "1+2+3+4+5+6+7+8+9+8+7+6+5+4+3+2+1=1x^4"

    Returns: 38753

  15. 19577

    29754

    "3y^4=2x^2+3"

    Returns: 2

  16. 737819

    579787

    "8y^3=1x^3+6x^3+0+0x^1"

    Returns: 1

  17. 1074

    127

    "4y^1+0y^7+6y^6=1x^9+4x^2+9x^3"

    Returns: 1

  18. 396

    4000

    "6y^7=0x^7+9x^5"

    Returns: 2

  19. 768130

    730570

    "3y^3+6=7x^3+0+2x^1+4x^2+1x^1+6+5x^1+9x^2+4x^2"

    Returns: 1

  20. 601298

    393054

    "9y^1+4+6=8x^3+6+3x^1+5x^1+8+4x^1+4x^3"

    Returns: 0

  21. 41272

    313026

    "6=1x^2+0x^1+7x^1"

    Returns: 0

  22. 459028

    179844

    "8y^3+2+7y^3+1=6x^1+9x^1+7x^3+3x^1"

    Returns: 0

  23. 193321

    298119

    "2y^2+6+9y^3+9+4+4y^2=0x^3+7x^2+2"

    Returns: 0

  24. 844769

    630308

    "4y^1=2x^3+6+1x^3+5x^1+9+9x^2+0+4"

    Returns: 52

  25. 913968

    79854

    "4+9+9y^3=9x^2+2x^3+9x^3+7x^1+9x^3+4x^2+8x^1+6x^1"

    Returns: 0

  26. 195594

    720962

    "0y^3+0+5y^2=8x^2+9x^2+9x^1+6+9x^3+4x^2+4x^3+5x^3"

    Returns: 1

  27. 838804

    553012

    "1y^2=6x^3+0+7x^2+6"

    Returns: 0

  28. 208291

    751108

    "8y^1=5x^2"

    Returns: 145

  29. 133939

    993645

    "8y^1+3y^2=8x^3+5x^1+6x^1+0x^2"

    Returns: 1

  30. 627417

    759268

    "7y^2+5y^1+0y^3+5+5y^3+4y^3+4y^2=8x^1"

    Returns: 0

  31. 294538

    499256

    "7y^2+2y^3+8y^2=5x^1+5x^2+6x^2+4"

    Returns: 0

  32. 138729

    873811

    "1y^3+2+1y^3+6y^3+3y^3+5+1+1y^1=0x^2+4+3x^1+7x^3"

    Returns: 0

  33. 507354

    617359

    "7+6y^1+2y^1=0x^2+1x^2+1+0x^1+5+2x^2+8x^2"

    Returns: 0

  34. 676517

    838116

    "5y^2+6y^2+4y^1+4y^2+0y^2+4+7y^1+3y^3=5x^2"

    Returns: 1

  35. 344471

    705234

    "9y^2+2+1y^3=0x^3"

    Returns: 0

  36. 773891

    891898

    "3y^2+2+3y^1=0x^2+9x^3+4x^3"

    Returns: 0

  37. 697433

    579886

    "3y^3+8y^2=1x^2+7+3x^3+2x^3+6x^3"

    Returns: 0

  38. 843297

    86446

    "8y^2+8y^3+4+3y^1=2x^3+9x^1+1x^1+9x^2"

    Returns: 0

  39. 1000000

    1000000

    "1=1"

    Returns: 1000002000001

  40. 1000000

    1000000

    "1+1=2"

    Returns: 1000002000001

  41. 1000000

    1000000

    "2+2=4"

    Returns: 1000002000001

  42. 1000000

    1000000

    "0y^3=0x^1"

    Returns: 1000002000001

  43. 1000000

    1000000

    "2y^1=1x^1"

    Returns: 500001

  44. 1000000

    1000000

    "1y^1=2x^1"

    Returns: 500001

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.
This problem was used for: