QuadraticEquations | Topcoder Archive

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*t²+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.

Definition

Class:: QuadraticEquations
Method:: howMany
Parameters:: int, int, int, int, int
Returns:: long
Method signature:: long howMany(int x, int y, int d, int z, int k)
(be sure your method is public)

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

```
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
```
5
```
```
1
```
```
3
```
```
4
```
```
10
```
```
Returns: 1
```
The equation 0*x2+0*x+0=0 always holds.
```
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.
```
0
```
```
-1
```
```
4
```
```
-1
```
```
2
```
```
Returns: 7
```
It is still 2.
```
-1
```
```
3
```
```
3
```
```
2
```
```
1000000
```
```
Returns: 153847
```
```
2
```
```
0
```
```
1
```
```
3
```
```
5
```
```
Returns: 11
```

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.