Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

skp1893's blog

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

How can I approach for this problem ?

8085 Divisors (Link)

The number of divisor function or d(n) is a very interesting function in number theory. It denotes the number of positive divisors of a particular number. For example d(24) = 8 as 24 has eight divisors 1, 2, 3, 4, 6, 8, 12 and 24 . In mathematics factorial of a positive integer number n is written as n! and is defined as below: n! = 1 × 2 × 3 × · · · × n

Another interesting function AF(n) (Again factorial in short) is defined as: AF(n) = 1! × 2! × 3! × . . . × n!

Given n , your job is to find the value of d(AF(n)).

Input The input file contains at most 101 lines of inputs. Each line contains an integer n (0 < n < 5000001) . Input is terminated by a line containing a single zero. This value should not be processed.

Output For each line of input produce one line of output.

This line contains the modulo 100000007 (10^8 + 7) of d(AF(n)).

Sample Input 1 2 3 4 100 0

Sample Output 1 2 6 18 59417661

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

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

Auto comment: topic has been updated by skp1893 (previous revision, new revision, compare).

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

First try to understand what happens for n = p^k for a prime p. The divisors are: p^0, p^1, … p^k. The number of divisors of them are: 1, 2, … k+1. And there summation is something like (k+1)(k+2)/2. Now try to find the answer for: p^a*q^b where p and q are primes.As the function is multiplicative the answer is (a+1)(a+2)/2.(b+1)(b+2)/2. So I think now you know what you need to do. Yes, First prime factorize n!.Then The final answer is multiple of (k+1)(k+2)/2 for all prime power k of p in n!. Now The only catch is that, for each prime p we need to find the power of p in n!, which is a common number theory subproblem.

Hope it helps.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    4! = 2^3 * 3^1. From what you said the answer should be (4*5/2)*(2*3/2) = 30, but samples says the answer is 18.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +6 Vote: I do not like it

      Actually samples are wrong. The answer for 4! is 30.

      4!=24 has divisors 1,2,3,4,6,8,12,24 where each of this have number of divisors 1,2,2,3,4,4,6,8 and sum of these are 30

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Alas you misunderstood the problem. AF(4) = 1! * 2! * 3! * 4! = 288 = 25 * 32 so d(288) = 6 * 3 = 18.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          Well, now it seems like I misunderstood the problem. Sorry for the inconvenience.

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

The number of some prime p occurring in the prime factorization of n! is . So the answer to the query is

Lets denote and (or ). Then the sum

can be calculated in O(1). So we get the answer as

The code

UPD: fixed formatting.