This problem is from ACM ICPC Dhaka Regional 2018 (Contest Link)

How can I approach for this problem?

Problem Satement:

The function d(n) denotes the number of positive divisors of an integer n. For example d(24) = 8, because there are 8 divisors of 24 and they are 1, 2, 3, 4, 6, 8, 12 and 24. The function sndd(n) is a new function defined for this problem. This denotes “The summation of number of divisors of the divisors” of an integer n. For example,

sndd(24) = d(1) + d(2) + d(3) + d(4) + d(6) + d(8) + d(12) + d(24) = 1 + 2 + 2 + 3 + 4 + 4 + 6 + 8 = 30.

Given the value of n, you will have to find sndd(n!), here n! means factorial of n. So n! = 1 × 2 × 3 × … × n.

Input The input contains at most 1000 lines of test cases. Each line contains a single integer that denotes a value of n (1 ≤ n ≤ 10^6). Input is terminated by a line containing a single zero.

Output For each line of input produce one line of output. This line contains an integer that denotes the modulo 10000007 (or 10^7 + 7) value of sndd(n).

Sample Input 4 5 0

Sample Output 30 90

Sorry, misunderstood the problem.

Your function sndd is multiplicative. Meaning that

`sndd(p_1^e_1 * p_2^e_2 *...* p_k^e_k) = sndd(p_1^e_1) * sndd(p_2^e_2) * ... * sndd(p_k^e_k)`

Also

`sndd(p_1^e_1) = (e_1+2)*(e_1+1)/2`

.It should be straight-forward with those observations.

I think you can precompute for each n, value of sndd

sndd(n!) = d(1) + d(2) + d(3) + .... d(n).

d(n) can be calculated using SPF in logn

is not that sum, it is:

This includes far more than

ndivisors.But I like the idea to precalculate for each

n. Start out withn= 1 and keep track of the prime-factorization ofn!. When you go fromnton+ 1 you only need to add the prime factors ofn+ 1. You can then calculate by the using the fact that it is multiplicative just like fruwajacybyk said.I have found the editorial for this contest (LINK)