JOIN
Get Time

   Problem Statement  

 Problem Statement for SparseFactorialDiv2

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. It is guaranteed that divisor will be a prime number. Compute and return the number of integers n between lo and hi, inclusive, such that F(n) is divisible by divisor.
 

Definition

    
Class:SparseFactorialDiv2
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 997, inclusive.
-divisor will be a prime number.
 

Examples

0)
    
4
8
3
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 3 but F(5) and F(8) are not.
1)
    
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.
2)
    
1
1000000000000
2
Returns: 999999999999
Watch out for the overflow.
3)
    
16
26
11
Returns: 4
4)
    
10000
20000
997
Returns: 1211
5)
    
123456789
987654321
71
Returns: 438184668

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.

This problem was used for:
       Single Round Match 596 Round 1 - Division II, Level Three