PROBLEM STATEMENT

Consider a circle in the plane.


You are given an int places. This is the number of places that are equally spaced along the 
perimeter of the circle, i.e., the distance between any two consecutive places is equal.
The places are numbered 0 to places-1 in clockwise order, starting at an arbitrary place.


We will now draw red points in some of the places. The number of red points is given as an int 
points. As the number of points may be large, we will generate them using a simple process that is 
described below.


Finally, once all points are generated, your task is to find and return the number of right 
triangles that have all three vertices in red points.


To generate the points, you are given three ints a, b, and c.
For n = 0, 1, 2, 3, ..., points-1, execute the following steps:


Compute P[n] = (a*n*n + b*n + c) modulo places.
Starting at P[n], find the first place in the clockwise direction that does not contain a red point.
Put a red point onto that place.


DEFINITION
Class:RightTriangle
Method:triangleCount
Parameters:int, int, int, int, int
Returns:long long
Method signature:long long triangleCount(int places, int points, int a, int b, int c)


NOTES
-A right triangle is a triangle with non-zero area in which one of the angles is exactly 90 degrees.
-For any valid input the answer fits into a long long (i.e., a signed 64-bit integer variable).


CONSTRAINTS
-places will be between 1 and 1,000,000, inclusive.
-points will be between 0 and 100,000, inclusive.
-points will not be greater than places.
-a will be between 0 and 1,000,000, inclusive.
-b will be between 0 and 1,000,000, inclusive.
-c will be between 0 and 1,000,000, inclusive.


EXAMPLES

0)
9
3
0
3
0

Returns: 0

The points are placed on places 0, 3, and 6. The resulting triangle is not a right triangle (in 
fact, it is equilateral).

1)
40
3
5
0
0

Returns: 1

This time the red points are on places 0, 5, and 20. The only triangle determined by these points 
is a right triangle.

2)
4
4
16
24
17

Returns: 4

This time the formula for the next place always gives the output 1. Hence the points are placed on 
places 1, 2, 3, and 0, in this order. Each of the four triangles determined by these points is a 
right triangle.

3)
1000000
47000
0
2
5

Returns: 0

An awful lot of obtuse triangles.

4)
200000
700
123456
789012
345678

Returns: 6980

Watch out for integer overflow when computing P[n].

 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)2010, TopCoder, Inc. All rights reserved.