QuadraticEquations
SRM 327 · 2006-11-22 · by Petr
SRM 327 · 2006-11-22 · by Petr · Math
Problem Statement
Problem Statement
Young Andrew has just learned about quadratic equations. He was quite amazed by the fact that their
solutions could look like (5+sqrt(3))/4, so he wants to dig into this issue. More specifically, given five numbers x, y, d, z and k, he wants to find the number of equations a*t2+b*t+c=0 such that (x+y*sqrt(d))/z is a solution of the equation (i.e., when substituting it for t the equation holds) and a, b and c are integers, -k <= a, b, c <= k. Notice that the equations he's looking for are not necessarily quadratic, i.e., a is allowed to be zero, as is b and/or c.
Constraints
- x, y and z will be between -1000 and 1000, inclusive.
- z will not be equal to 0.
- d will be between 1 and 1000, inclusive.
- k will be between 0 and 1000000 (106), inclusive.
Examples
0)
5 1 3 4 30 Returns: 3
The three possible equations are: 0*x2+0*x+0=0, 8*x2-20*x+11=0, -8*x2+20*x-11=0
1)
5 1 3 4 10 Returns: 1
The equation 0*x2+0*x+0=0 always holds.
2)
2 0 1 1 2 Returns: 7
The value described is simply 2. The equations are 0*x2+0*x+0=0, 0*x2+1*x-2=0, 0*x2-1*x+2=0, 1*x2-1*x-2=0, -1*x2+1*x+2=0, 1*x2-2*x+0=0, -1*x2+2*x+0=0.
3)
0 -1 4 -1 2 Returns: 7
It is still 2.
4)
-1 3 3 2 1000000 Returns: 153847
Submissions are judged against all 83 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class QuadraticEquations with a public method long long howMany(int x, int y, int d, int z, int k) · 83 test cases · 2 s / 256 MB per case