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

Auto comment: topic has been updated by skp1893 (previous revision, new revision, compare).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.

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.

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

Alas you misunderstood the problem.

AF(4) = 1! * 2! * 3! * 4! = 288 = 2^{5}* 3^{2}so d(288) = 6 * 3 = 18.Well, now it seems like I misunderstood the problem. Sorry for the inconvenience.

The number of some prime

poccurring in the prime factorization ofn! is . So the answer to the query isLets denote and (or ). Then the sum

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

The codeUPD: fixed formatting.