### Problem Statement

A particular star system consists of a single star, with N planets orbiting it. Each planetary orbit is a perfect circle of distinct radius centered on the star and all orbits lie in the same 2-D plane. The planets move along their circular paths with constant speed and planet i completes 1 full orbit in the time given by the absolute value of periods[i]. periods[i] will be positive if planet i orbits clockwise and negative if it orbits counter-clockwise. A k-planetary alignment occurs when an infinite straight line exists, passing through the center of the star and through the centers of at least k of the planets. A N-planetary alignment occurs at time T = 0, i.e., all the planets lie in a line at this time (see notes for clarification). Return the number of distinct times between T1 and T2, inclusive, when a k-planetary alignment occurs.

### Definition

 Class: KPlanetaryAlignment Method: number Parameters: int[], int, int, int Returns: int Method signature: int number(int[] periods, int k, int T1, int T2) (be sure your method is public)

### Notes

-The constraints ensure the return value will fit in a signed 32-bit integer.
-Alignments can occur with the planets either on the same side of the star or diametrically opposite each other.
-The configuration of the planets at T = 0 (i.e., whether the planets are all on the same side, or some are diametrically opposite) makes no difference to the answer.

### Constraints

-periods will contain between 2 and 5 elements, inclusive.
-Each element of periods will be a non-zero integer between -100 and 100, inclusive.
-The elements of periods will be distinct.
-k will be between 2 and the number of elements in periods, inclusive.
-T2 will be between 0 and 50,000,000 (5 * 10^7), inclusive.
-T1 will be between 0 and T2, inclusive.

### Examples

0)

 `{8,40}` `2` `0` `20`
`Returns: 5`
 Here, the first planet is rotating 5 times as quickly as the second. Ater 5 seconds, the first will have completed 5/8 of an orbit, while the second will have completed 5/40 = 1/8 of an orbit. They are therefore diametrically opposite and this is the first 2-alignment after time 0. Further 2-alignments happen at T = 10, 15 and 20.
1)

 `{8,24,40}` `2` `0` `20`
`Returns: 8`
 With an additional planet, 2-alignments happen at T = 0, 5, 6, 10, 12, 15, 18, 20.
2)

 `{8,24,40}` `3` `0` `100`
`Returns: 4`
 3-alignments of the same set of planets happen at T = 0, 30, 60, 90.
3)

 `{-10,10}` `2` `2` `26`
`Returns: 10`
 Now that the planets are rotating in opposite directions, 2-alignments occur every 2 1/2 seconds.
4)

 `{-1,2,3,4,5}` `3` `10000` `50000`
`Returns: 53333`
5)

 `{-1,1}` `2` `0` `50000`
`Returns: 200001`
6)

 `{-2,91,87,77,71}` `4` `0` `50000000`
`Returns: 1471`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13505&pm=8673

StevieT

#### Testers:

PabloGilberto , Olexiy , gawry , ivan_metelsky

Math, Search