Editorial for DIVFACT - Divisors of factorial problem -- SPOJ - UCS - Unleash-Coding-Skills

Monday, 5 March 2018

Editorial for DIVFACT - Divisors of factorial problem -- SPOJ - UCS



This is editorial for DIVFACT problem:

http://www.spoj.com/problems/DIVFACT/

Given a number, find the total number of divisors of the factorial of the number.
Since the answer can be very large, print answer modulo 109+7.

Input

The first line contains T, number of testcases.
T lines follows each containing the number N.

Output

Print T lines of output each containing the answer.

Example

Input:
3
2
3
4

Output:
2
4
8

Constraints

1 <= T <= 500
0 <= N <= 50000
In this first precalculate the primes  in range from 1 to 50000.Otherwise if you
calucalate for each iteration.
#include <iostream>

using namespace std;

 bool isPrime[50001];

 #define mod 1000000007

void sieve(long long N) {
    for(long long i = 0; i <= N;++i) {
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    for(long long  i = 2; i * i <= N; ++i) {
         if(isPrime[i] == true) {
             for(long long j = i * i; j <= N ;j += i)
                 isPrime[j] = false;
        }

    }
}
int main() {
    sieve(50000);
    long long int t,i,j,k,n,count=0,r,e,ans;
    cin>>t;
    for(long int ii=0;ii<t;ii++)
    {
          i=1;
          cin>>n;
          ans=1;
          while(1)
          {
                 if(i>n)
                 break;
  //if it is prime do calculation else simply increment the value of 'i'
//and finally print the value for (ans%mod) in new line
                if(isPrime[i])
                {
                     r=i;
                     e=n;
                      count=0;
                     while(int(e/r)>0)
                     {
                           count+=int(e/r);
                           r*=i;
                           
                     }
              
                  ans=(ans*(count+1))%mod;
                }
                i++;
          }
          cout<<ans%mod<<endl;
    }
    return 0;
}
 

Happy Coding...

Share your views in comments

No comments:

Post a comment