### Sukarna_Paul's blog

By Sukarna_Paul, history, 18 months ago, ,

How can I approach for this problem ?

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

• +1

 » 18 months ago, # |   0 Auto comment: topic has been updated by skp1893 (previous revision, new revision, compare).
 » 18 months ago, # |   +6 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.
•  » » 18 months ago, # ^ |   +6 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.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   +6 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
•  » » » » 18 months ago, # ^ |   +6 Alas you misunderstood the problem. AF(4) = 1! * 2! * 3! * 4! = 288 = 25 * 32 so d(288) = 6 * 3 = 18.
•  » » » » » 18 months ago, # ^ |   +6 Well, now it seems like I misunderstood the problem. Sorry for the inconvenience.
 » 18 months ago, # | ← Rev. 6 →   +6 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#include #if defined( _WIN32 ) typedef __int64 az_int64_t; typedef unsigned __int64 az_uint64_t; #define I64(x) x ## I64 #define F64 "I64" #else typedef long long az_int64_t; typedef unsigned long long az_uint64_t; #define I64(x) x ## ll #define F64 "ll" #endif #define MODN 100000007 #define LIMIT 5000000 const int pd[210] = { 10,0,0,0,0,0,0,0,0,0,2,0,4,0,0,0,2,0,4,0,0,0,6,0,0,0,0,0,2,0,6,0,0,0,0,0,4, 0,0,0,2,0,4,0,0,0,6,0,0,0,0,0,6,0,0,0,0,0,2,0,6,0,0,0,0,0,4,0,0,0,2,0,6,0, 0,0,0,0,4,0,0,0,6,0,0,0,0,0,8,0,0,0,0,0,0,0,4,0,0,0,2,0,4,0,0,0,2,0,4,0,0, 0,8,0,0,0,0,0,0,0,6,0,0,0,0,0,4,0,0,0,6,0,0,0,0,0,2,0,4,0,0,0,6,0,0,0,0,0, 2,0,6,0,0,0,0,0,6,0,0,0,0,0,4,0,0,0,2,0,4,0,0,0,6,0,0,0,0,0,2,0,6,0,0,0,0, 0,4,0,0,0,2,0,4,0,0,0,2,0,10,0,0,0,0,0,0,0,0,0,2,0 }; #define PIS(_n) (pbits[(_n)>>5] & (1u << ((_n) & 0x1f))) #define PSET(_n) (pbits[(_n)>>5] |= (1u << ((_n) & 0x1f))) unsigned int pbits[LIMIT/32+1]; /* Prime list up to LIMIT */ int pr[350000], pc = 0; void gen( void ) { int i, j; pr[pc++] = 2; pr[pc++] = 3; pr[pc++] = 5; pr[pc++] = 7; for( i = 11; i <= LIMIT; i += pd[(i-1)%210]) if( !PIS(i) ) { pr[pc++] = i; if( i <= 2236 ) { int limit = LIMIT / i; for( j = i; j <= limit; j += pd[(j-1)%210]){ int v = j * i; PSET( v ); } } } } int solution( int num ) { az_int64_t res = 1; int i; for( i = 0; i < pc && pr[i] <= num; ++i) { int k, p = pr[i], limit = num / pr[i], sum = 0; for(;;) { int a = num / p, b = num % p; az_int64_t v = a; v = (v * (a+1)) / 2 * p - v * (p - b - 1); v %= MODN; sum += (int) v; if( sum >= MODN ) sum -= MODN; if( p > limit ) break; p *= pr[i]; } res *= sum + 1; res %= MODN; } return (int) res; } int main( void ) { int n; gen(); while( scanf( "%d", &n) == 1 && n > 0 ) printf( "%d\n", solution( n )); return 0; } UPD: fixed formatting.