Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Sukarna_Paul's blog

By Sukarna_Paul, history, 12 months ago, ,

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

• +5

 » 12 months ago, # | ← Rev. 2 →   0 Sorry, misunderstood the problem.
 » 12 months ago, # |   +29 Your function sndd is multiplicative. Meaning thatsndd(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.
 » 12 months ago, # |   0 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
•  » » 12 months ago, # ^ | ← Rev. 3 →   -9 is not that sum, it is:This includes far more than n divisors.But I like the idea to precalculate for each n. Start out with n = 1 and keep track of the prime-factorization of n!. When you go from n to n + 1 you only need to add the prime factors of n + 1. You can then calculate by the using the fact that it is multiplicative just like fruwajacybyk said.
 » 12 months ago, # |   0 I have found the editorial for this contest (LINK)