SparseFactorial | Topcoder Archive

Problem Statement

For an integer n, let F(n) = (n - 0^2) * (n - 1^2) * (n - 2^2) * (n - 3^2) * ... * (n - k^2), where k is the largest integer such that n - k^2 > 0. You are given three longs lo, hi and divisor. Compute and return the number of integers n between lo and hi, inclusive, such that F(n) is divisible by divisor.

Definition

Class:: SparseFactorial
Method:: getCount
Parameters:: long, long, long
Returns:: long
Method signature:: long getCount(long lo, long hi, long divisor)
(be sure your method is public)

Constraints

lo will be between 1 and 1,000,000,000,000, inclusive.
hi will be between lo and 1,000,000,000,000, inclusive.
divisor will be between 2 and 1,000,000, inclusive.

Examples

```
4
```
```
8
```
```
6
```
```
Returns: 3
```
The value of F(n) for each n = 4, 5, ..., 8 is as follows. F(4) = 4*3 = 12 F(5) = 5*4*1 = 20 F(6) = 6*5*2 = 60 F(7) = 7*6*3 = 126 F(8) = 8*7*4 = 224 Thus, F(4), F(6), F(7) are divisible by 6 but F(5) and F(8) are not.
```
9
```
```
11
```
```
7
```
```
Returns: 1
```
F(9) = 9*8*5 = 360 F(10) = 10*9*6*1 = 540 F(11) = 11*10*7*2 = 1540 Only F(11) is divisible by 7.
```
1
```
```
1000000000000
```
```
4
```
```
Returns: 999999999996
```
Watch out for the overflow.
```
55
```
```
66
```
```
98
```
```
Returns: 7
```
```
999990
```
```
999999
```
```
589824
```
```
Returns: 7
```
```
100000000
```
```
100000050
```
```
749910
```
```
Returns: 8
```
```
7777777776
```
```
7777777777
```
```
994009
```
```
Returns: 1
```

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.