BBSYSTEM - editorial

PROBLEM LINKS

Practice
Contest

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 kNMAX.

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 NNMAX, 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 = i
i+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.

1 Like

Problem : Box in a Box

Idea is to take a number as input and print a pattern of boxes
If input is 2, two boxes are to be printed - one inside the other
Smallest box will be of size 33, the next bigger box will be 55, the next one will be 77, so on and so forth
For input 1, then draw a box of dimensions 3
3
For input 2, outer box will be 55, inner will be 33
For input 3, outer box will be 77, with 2 more inner boxes
So for n, outermost box will be n
2 +1 in size, with (n-1) inner boxes
All boxes will be top left aligned as shown in the figure

Input Format:

First line of input contains a number N

Output Format:

Print N nested boxes

Constraints:

0 < N < 25

//