Connection Status:
Competition Arena > SparseFactorial

SparseFactorial

SRM 596 · 2013-06-25 · by ir5

SRM 596 · 2013-06-25 · by ir5 · Math
Class Name: SparseFactorial
Return Type: long
Method Name: getCount
Arg Types: (long long, long long, long long)
Problem Statement

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.

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.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
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.

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
4
Returns: 999999999996

Watch out for the overflow.

3)
55
66
98
Returns: 7
4)
12
56
100
Returns: 24

Submissions are judged against all 133 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SparseFactorial with a public method long long getCount(long long lo, long long hi, long long divisor) · 133 test cases · 2 s / 256 MB per case

Submitting as anonymous