You are not logged in. Please login at www.codechef.com to post your questions!

×

NUMFACT - Editorial

7
2

Author: Vamsi Kavala
Tester: Roman Rubanenko
Editorialist: Bruno Oliveira

PROBLEM LINKS

Practice
Contest

DIFFICULTY

Cakewalk

PRE-REQUISITES

Simple Math, Integer Factorization

Problem:

You are given a very large number represented as a product of N numbers. Given this number representation, you need to find the number of distinct factors of the original number which is formed by the product of given N numbers.

Quick Explanation:

We can factorize each one of the N given numbers into its prime factors. Then we find the number of occurrences of each prime factor, say they are a1, a2,...aK, if we have K distinct prime factors. Our answer is simply: (a1+1)(a2+1)(...)*(aK+1).

Detailed Explanation:

This problem relies on some knowledge of divisor function. Divisor functions returns the number of positive and distinct divisors of a number. Let's call it d(x).

  • Some properties of the divisor function:

    We now look into some important properties of the divisor function:

    For a prime number p, we have d(p) = 2, as there are only two numbers which divide a prime number:1 and itself.

    Now, it's a known fact that this function is multiplicative but not completely multiplicative. This means that if two numbers, say, a and b are there such that gcd(a, b) = 1, then the following holds: d(a*b) = d(a)*d(b).

This allows us to deduce the important relationship, that is the key of solving this problem:

For a prime number, p, we have: d(p^n) = n+1.

Now, it's easy to understand that all we need to do is to factorize all the N given numbers into its prime factors, and, for each prime factor we also need to count how many times it appears (that is, we need to know the exponent of each prime factor).

Once we have this count with us (which can be done using integer factorization and for example, the set and map data structures, one to guarantee uniqueness of the factors and the other to save the number of occurences for each unique prime factor), all we need to do is to multiply all these numbers plus one together and we will obtain our answer.

As an example, consider the number:

504 = 2^3 * 3^2 * 7^1

The number of distinct divisors of 504 is then (3+1) * (2+1) * (1+1) = 24.

Applying this process to all numbers yields the answer to the problem :)

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Tester's solution will be uploaded soon.

Useful Links

What is a multiplicative function?
More information on the divisor function

This question is marked "community wiki".

asked 30 Jun '13, 14:10

kuruma's gravatar image

2★kuruma
17.5k72143208
accept rate: 8%

wikified 30 Jun '13, 15:12

abhijeetpandey's gravatar image

3★abhijeetpandey ♦♦
30171012

In your code, you are checking whether a[i] == 1 towards the end. But can you give me a case where it wont be equal to 1. Wont the prime numbers stored in the list make sure that the smallest number is being factorized first and then proceed to the largest??

(31 Oct '13, 22:25) trial0070★

Any special reason for using char type of array for storing primes by setter ?

(22 Jan '16, 03:21) shubham992★

@shasha1s2 wen u update 'other' array to count prime u do not account for the fact that the prime number being counted may be the same..in other words, the value of other[i] (according to your code) will never be more than 1...going by that the test case 5 999983 999983 999983 999983 999983 will give 32 as per your code, while ans is 6.

link

answered 30 Jun '13, 16:40

amitrc17's gravatar image

5★amitrc17
62116
accept rate: 0%

edited 30 Jun '13, 16:52

thanx @amitrc17 got my error...

(30 Jun '13, 19:23) shasha1s23★

@roshi...it will most certainly give a TLE as the time complexity is very high!!!!

try using Sieve of Eratosthenes....see the time difference....Naive approach....seive!!!

link

answered 30 Jun '13, 23:08

kunal361's gravatar image

4★kunal361
6.0k133272
accept rate: 21%

A simple modification of Sieve of Erastothenes will also prove to be helpful. The following is what I used.

f[i] == 0 if i is prime, and if i is prime, then f[i] will have the smallest prime that will divide it.

for (int i = 2; i <= N; i++) if (!f[i]) for (int j = i+i; j <= N; j += i) if (!f[j]) f[j] = i;

f[i] will help a lot to find all the prime divisors of a number.

(01 Nov '13, 15:03) turuthok3★

http://www.codechef.com/viewsolution/2894661

A shorter solution with the same concept + the subtle modification of the sieve to store prime factor info.

(01 Nov '13, 15:06) turuthok3★

@shubham26 if you look at the constraints .They are :- N<=10 Ai<=1000000

and as in your code you multiply each Ai to get a number which is product of all of them. Suppose if all the numbers are 10^6 and N=10 and they are multiplied N times,the number becomes (10^6)^10=10^60 which is far beyond the range of long(range of the order 10^9)( (even its far away from long long(range of the order 10^18)).

link

answered 01 Jul '13, 08:45

dhruvagga's gravatar image

3★dhruvagga
174225
accept rate: 0%

@dhruvagga : thanks..I got it. :)

(01 Jul '13, 14:55) shubham262★

In the setter's solution what is the use of this code fragment if(a[i]!=1) { if(m.find(a[i])!=m.end()) m[a[i]]++; else m.insert(MP(a[i],1));

from line 85 to 90 I put that in comments and ran the program and it gave the correct o/p for test cases. I don't understand it's use. After dividing with all the prime numbers shouldn't a[i] necessarily be 1.

link

answered 12 Jul '13, 23:30

tdk93's gravatar image

3★tdk93
3026
accept rate: 0%

edited 12 Jul '13, 23:38

Can you tell me where my code fails... I have applied same concept i think.. http://www.codechef.com/viewsolution/2304397

link

answered 30 Jun '13, 14:15

shasha1s2's gravatar image

3★shasha1s2
-1112
accept rate: 0%

it not works for prime numbers above 1000 like 1009,1013 etc

link

answered 30 Jun '13, 14:23

goel_coder's gravatar image

2★goel_coder
35125
accept rate: 0%

it works.. I have used "other" array for those primes Can u provide any testcase where it fails..

(30 Jun '13, 14:35) shasha1s23★

Either you can use a sieve to extend your primes array or just put more primes in the primes array.

here's a sample code for sieve. http://ideone.com/arhRSv

link

answered 30 Jun '13, 15:49

dhruvagga's gravatar image

3★dhruvagga
174225
accept rate: 0%

edited 30 Jun '13, 15:57

It gives a TLE when i use the function 'prime' to find the prime factorisation of the number.Can someone please tell me where i went wrong? Thanks in advance. Here is the link to my code : http://ideone.com/kgzICq

link

answered 30 Jun '13, 22:52

roshi's gravatar image

2★roshi
614919
accept rate: 0%

What is wrong in my code?? http://ideone.com/Y5mZLP It gives correct answers to all the numbers with which I have checked. :(

link

answered 01 Jul '13, 02:09

shubham26's gravatar image

2★shubham26
6115
accept rate: 0%

edited 01 Jul '13, 02:22

Can anyone provide critical input. My solutions keeps getting WA, however, when comparing to AC code gives same output.

from sys import stdin
from collections import Counter
from math import sqrt,ceil

def primes(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    correction = (n%6>1)
    n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
    sieve = [True] * (n/3)
    sieve[0] = False
    for i in xrange(int(n**0.5)/3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      ((k*k)/3)      ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
        sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&1))/6-1)/k+1)
    return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]

def factor(n):
    upper = n
    i = 0
    while sieve[i] <= ceil(sqrt(upper)):
        while n%sieve[i]==0:
            n/=sieve[i]
        if sieve[i] not in factors:
        factors[sieve[i]]=0
            factors[sieve[i]]+=1
        i+=1
    if(n>1):
        if upper not in factors:
            factors[upper]=0
        factors[upper]+=1

sieve = primes(10000)
factors = {}

def solve():
    N = int(stdin.readline())
    numbers = map(int,stdin.readline().split())
    #print([i for i in numbers])
    factors.clear()
    for num in numbers:
        factor(num)
    tot = 1
    for num in factors:
        #print("fac",num,factors[num])
        tot *= (factors[num]+1)
    print tot


def main():
    tc = int(stdin.readline())
    for i in range(1,tc+1):
        solve()


if __name__=="__main__":
    main()
link

answered 28 Oct '13, 00:25

Niels_ten_Dijke's gravatar image

2★Niels_ten_Dijke
1
accept rate: 0%

whats the problem wid following ? i got a WA

#include<stdio.h>
#include<math.h>
int primes[1000000];
int a[1000000];
void gen_primes(int n)
{
 int i,j;
 for(i=0;i<n;i++)
  primes[i]=1;
 for(i=2;i<=(int)sqrt(n);i++)
 {
  if(primes[i])
  {
   for(j=i;j*i<n;j++)
   {
    primes[i*j]=0;
   }
  }
 }
}
main()
{
 int t,n,i;
 long long int p,x;
 scanf("%d",&t);
 while(t--)
 {
  scanf("%d",&n);
  for(i=0;i<(int)sqrt(n);i++)
  {
   a[i]=0;
  }
  gen_primes(n);
  while(n--)
  {
   scanf("%lld",&x);
   for(i=2;i<=(int)sqrt(n);i++)
   {
    if(primes[i])
    {
     if(x%i==0)
     {
      a[i]=a[i]+(long long int)((double)log(x)/(double)log(i));
     }
    }
   }
  }
  p=1;
  for(i=2;i<=(int)sqrt(n);i++)
  {
   if(a[i])
   {
    p=p*(a[i]+1);
   }
  }
  printf("%lld\n",p);
 }
 return 0;
}
link

answered 27 Jun '14, 18:31

karankapoor's gravatar image

2★karankapoor
-112
accept rate: 0%

my code is running fine on the first time.. but in second test case giving erronous output.. please help..

#include<stdio.h>

int freq[1000000];
int sum;

void count(long long int x)
{
 int i;
 for(i=2;;i++)
 {
  while(x%i==0)
  {
   freq[i]++;
   x=x/i;
   sum++;
  }
  if(x==1)
   break;
 }
}


int main(void)
{
 int t,n,p,y,i;
 long long int x;
 scanf("%d",&t);
 while(t--)
 {
  p=1;
  y=0;
  sum=0;
  scanf("%d",&n);
  for(i=0;i<n;i++)
   freq[i]=0;
  while(n--)
  {
   scanf("%lld",&x);
   count(x);
  }
  for(i=0;;i++)
  {
   if(freq[i]!=0)
   {
    p=p*(freq[i]+1);
    y=y+freq[i];
    if(y==sum)
     break;
   }
  }
  printf("%d\n",p);
 }
 return 0;
}
link

answered 29 Jun '14, 22:36

karankapoor's gravatar image

2★karankapoor
-112
accept rate: 0%

Where Am i Going Wrong , Its Always SIGSEV and TLE on my Submission :'( , Plz help me Fast i Need to Brace up For IOI

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void solve(long long int *primes,long long int *n )
{


        long long int *z = (long long int *)calloc(1001,sizeof
                                               (long long int));

    while(*n>1)
    {
        for(long long int i=0;i<168;i++)
        {
            if(*n%primes[i]==0){z[i]++;*n= *n/primes[i];i--;}
        }

    }
    long long int prod=1;
    for(long long int k=0;k<168;k++)if(z[k]!=0)prod*=(z[k]+1);
    printf("%lld \n",prod);
    //for(long int i=0;i<n&&primes[i]!=0;i++)printf("%ld \n",primes[i]);
}
int main()
{
  long long int *primes;
    primes = (long long int *)calloc(1001,sizeof(long long int));
    primes[0]=2;
    primes[1]=3;
    long long int index=2;
    for(long long int z=5;z<=1001;z+=2)
    {
            long long int fact=0;
            for(long long int i=0;i<1001&&primes[i]!=0;i++)
            {
                if(z%primes[i]==0){fact++;break;};
            }
            if (fact==0)
            {
                primes[index]=z;
                index++;
            }
    }
    long long int t;
    scanf("%lld",&t);
    while(t--){
        long long int n,prod=1,temp;
    scanf("%lld",&n);
    for(long long int i=0;i<n;i++){scanf("%lld",&temp);prod*=temp;}

    solve(primes,&prod);
    }
}
link

answered 04 Nov '14, 17:12

siddharths067's gravatar image

1★siddharths067
7916
accept rate: 4%

edited 04 Nov '14, 19:13

I Even Tried Putting The Sieve Out , But Still i was only able to Solve only One Subtask !!! :'(

(04 Nov '14, 19:12) siddharths0671★

Hey whats wrong in my code here?


program FACTORS;

uses Math;
var
   t,n,num,product:longint;

function factors(fact:longint):longint;
var
   no:longint = 0;
   x:longint;
begin
    for x := 1 to floor(sqrt(fact)) do
    begin
    if fact mod x = 0 then 
    begin
    if x*x = fact then inc(no,1)
    else inc(no,2);
    end;
    end;
    factors := no;
end;
begin
    readln(t);
    while t <> 0 do
    begin
    readln(n);
    product := 1;
    while n <> 0 do
    begin
    read(num);
    product := product * num;
    dec(n);
    end;
    writeln(factors(product));
    dec(t);
    end;
end.

I am getting runtime error NZEC.

link

answered 24 Jun '15, 08:47

vinay_2003's gravatar image

1★vinay_2003
313
accept rate: 0%

I have been trying to debug my code for so long still not able to figure out why it is giving a WA for the basic cases. Please if anyone could tell me where am I going wrong? This is the link to my solution.
https://www.codechef.com/submit/complete/8669014

link

answered 30 Oct '15, 19:30

raunak_parijat's gravatar image

4★raunak_parijat
8726
accept rate: 0%

nice explanation. I used sieve of eratosthenes to get all prime factors of number

link

answered 19 Nov '15, 22:33

dhavalmehta's gravatar image

2★dhavalmehta
563
accept rate: 30%

https://www.codechef.com/viewsolution/14084014 WHY IS THIS SOLUTION GETTING A WA ON LAST CASE PLZ HELP!!

link

answered 05 Jun, 18:53

soheb17's gravatar image

4★soheb17
0
accept rate: 0%

-1
#include<stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    if(t>=1 && t<=100)
    {
        while(t--)
        {
            int n;
            scanf("%d",&n);
            if(n>=1&&n<=10)
            {
                long int a, total=1;
                while(n--)
                {
                    scanf("%ld",&a);
                    if(a>=2&&a<=1000000)
                    total*=a;
                }
                int count=0;
        for(int i=1;i<=total;i++)
        {
            if(total%i==0)
                count++;
        }
        printf("%d\n",count);
            }
        }
    }
    return 0;
}

why time limit exist????

link

answered 04 Oct '13, 17:20

habib_cse_ruet's gravatar image

0★habib_cse_ruet
0
accept rate: 0%

edited 04 Oct '13, 19:14

betlista's gravatar image

3★betlista ♦♦
16.8k49115225

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,344
×270
×45
×14

question asked: 30 Jun '13, 14:10

question was seen: 21,669 times

last updated: 05 Jun, 18:53