TopCoder problem "RightTriangle" used in SRM 473 (Division I Level Two)



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
Method signature:long triangleCount(int places, int points, int a, int b, int c)
(be sure your method is public)
    
 

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 (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].

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10976

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14155&pm=10976

Writer:

misof

Testers:

PabloGilberto , bmerry , ivan_metelsky

Problem categories:

Math, Search