PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
Basic Observations: Let f(N, k) be the number of the integers no more than N which have exactly k divisors. For each k, f(N, k) balls can be put into f(N, k) boxes freely. The number of these patterns is f(N, k)! (factorial number). Therefore the answer is (g(N)-1) mod M, where g(N) = f(N, 1)! * f(N, 2)! * …, and M = 500009. Note that subtracting of one corresponds to the fact that initial state is not valid.
Some Tricks: By the definition, if N has k divisors, f(N, k) - f(N-1, k) = 1, otherwise f(N, k) - f(N-1, k) = 0. Therefore, we obtain g(N) = g(N-1) * f(N, k), where k is the number of the divisors of N. And, we can check the fact that g(NMAX) mod M = 0, where NMAX = 2229283, since f(NMAX, 8) = M. Thus, g(k) mod M = 0 for k ≥ NMAX.
To wrap up, now, our task is calculating the number of the divisors of N, for N < NMAX. The following is a pseudo code.
div[k] := the number of the divisors of k (this part is considered in the following)
sum[k] := 0
res[0] := 1
for(k = 1; k < NMAX; k++)
sum[div[k]] := sum[div[k]] + 1
res[k] := res[k-1] * sum[div[k]] mod M
foreach N in test cases
if N ≥ NMAX, print -1 mod M
else print res**[N]** - 1 mod M
First Approach: For each integer, calculate the number of the divisors of the integer independently. However, this approach is terrible slow. This approach should get Time Limit Exceeded.
Second Approach: This approach is, for each integer i, to increment the number of the divisors of the integers multiple of i. This approach run in O (NMAX log NMAX) time, but this approach is a bit slow for this problem. (This approach can get Accepted for the first version of this problem. However, the tester suggested this problem should be solved more faster!)
div[k] := 0
for(i = 1; i < NMAX; i++)
for(j = i; j < NMAX; j += i)
div[j] := div[j] + 1
Modified Second Approach: The fact “if k is a divisor of N, then N/k is also a divisor of N” can make Second Approach about twice faster. This approach can be Accepted if some optimizations are used, but this approach may get Time Limit Exceeded if implemented naively. For example, use unsigned char or short arrays instead of int arrays for optimizations.
div[k] := 0
for(i = 1; ii < NMAX; i++)
div[i*i] := div[i*i] + 1
for(j = ii+i; j < NMAX; j += i)
div[j] := div[j] + 2
Third Approach: Let the factorization of k be 2P 2 * 3
p 3 * 5
p[5] * …, then the number of the divisors of k is (p2+1) * (p3+1) * … This approach also can be Accepted if some optimizations are used, but sometimes get Time Limit Exceeded.
div[k] := 1
rest[k] := k
foreach prime number p such that p*p < NMAX
for(i = p; i < NMAX; i += p)
power := 0
while(p divides rest[i])
power := power + 1
rest[i] := rest[i] / p
div[k] := div[k] * (power + 1)
foreach k such that rest[k] > 1
div[k] := div[k] * 2
Fourth Approach (Model Solution): Let m[k] be the minimum prime divisor of k, and let the factorization of k be m[k]deg[k] * … Then the following recursion formula is hold:
Let i be k / m[k], then
If m[i] = m[k], then deg[k] = deg[i] + 1, and div[k] = div[i] * (deg [k]+1) / (deg[i]+1),
otherwise, deg[k] = 1, and div[k] = div[i] * 2.
This recursion formula can be proved by using the fact that the number of the divisors is (p 2 +1) * (p 3 +1) * … This approach run in about 1.5 sec if implemented naively in C/C++. Here, the following naive way is enough for calculating m[k].
m[k] := k
foreach prime number p such that p*p < NMAX
for(i = p; i < NMAX; i += p)
if m[k] > p, then m[k] = p
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.