SparseFactorial
SRM 596 · 2013-06-25 · by ir5
SRM 596 · 2013-06-25 · by ir5 · Math
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 long s 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.
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