TopCoder SRM 596 - 1000: SparseFactorial

Problem Statement

定义“稀疏阶乘函数” F(x)= (x-0^2)*(x-1^2)*...*(x-k^2)，其中k=sqrt(x-1)，
求在[lo, hi]中有多少个正整数 x 满足 F(x) 是 m 的倍数。
数据范围：1 <= lo <= hi <= 10^12, 2 <= m <= 10^6

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 long , long long
Returns long long
Method signature long long getCount(long long lo, long long hi, long long divisor)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

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.

Test cases

input
- lo 4
- hi 8
- divisor 6
output
Returns 3
note
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.
input
- lo 9
- hi 11
- divisor 7
output
Returns 1
note
- 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.
input
- lo 1
- hi 1000000000000
- divisor 4
output
Returns 999999999996

note

Watch out for the overflow.
input
- lo 55
- hi 66
- divisor 98
output
Returns 7
input
- lo 999990
- hi 999999
- divisor 589824
output
Returns 7
input
- lo 100000000
- hi 100000050
- divisor 749910
output
Returns 8
input
- lo 7777777776
- hi 7777777777
- divisor 994009
output
Returns 1

back to the menu

SRM 596 1 1000 SparseFactorial

Problem Statement

Definition

Limits

Constraints

Test cases