Sukarna_Paul's blog

By Sukarna_Paul, history, 5 weeks ago, In English,

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

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Sorry, misunderstood the problem.

»
5 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it -9 Vote: I do not like it

    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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I have found the editorial for this contest (LINK)