💡 Playing With Divisors Is Fun

#1

I didn’t understand the question and given test case eg when input is
3
1 1 1
N will be 235=30
product of divisor of 30 is
123561015*30=810,000
now we need to find number of divisors of 810000 , is it correct?
can you give some hint or method ?
Thank You.

#2

Yeah you are right you need to find the number of factors of 810000 which is 125. As the number of factors may be large for many numbers you’ll need to mod it by 10^9 + 7.

Hint :

  • Make the number P using number N in form of an array.
  • Use PnC to find number of divisors of P.

Example :

  • Say N = 30
    2 3 5
    1 1 1
  • Now P = 1 * 2 * ....... * 30 = 810000
    You need to understand that divisors of N are combinations of 2, 3 & 5.
    To make the array of P. You need to count the number of times 2, 3 & 5 will be picked in the divisors of N.
    As all the numbers are there only 1 time. there are 8 combinations of 2, 3 & 5 (000 001 010 011 100 101 110 111) where 0 means not picked and 1 means picked. We can see there are 8 divisors of 30.
    Using this we can make the array for P.
    P = 810000
    2 3 5
    4 4 4
    Now finding the number of divisors of P is easy.
    000 001 002 003 004 010 011 012 013 014 ........... 442 443 444 these will be all the divisors of P where xyz means picking x of 2, y of 3 and z of 5.
    You can clearly see this is just a base 5 counting with 3 bits. so there will be 5^3 numbers b/w 000 .... 444 which is 125.
    I hope this helps you.
#3

I am only considering 2 3 5 because 810000 is a number made by multiples of divisors of a number which has factor as 2^1 3^1 and 5^1. There are no other prime factors of 810000. They wouldn’t exist as 810000 is a number made by multiplying numbers containing 2, 3 and 5. And no other prime number can be made by multiplication of other two prime numbers as that is against the defination of prime numbers.

So 810000 will also have these prime factors with higher powers 2^x 3^y and 5^z and I have told you the way to find out xyz in the post. They all came out to be 4 i.e. x = y = z = 4. and then we find out number of possible divisors of 810000 by using PnC.

As now you know you have four 2s, four 3s and four 5s. So I know I can pick zero of 2s ....upto.... four of 2s. Similarly for 3s and 5s. So that is basically going from 000........to..........444 that means 2^0 * 3 ^0 * 5^0 .........to......... 2^4 * 3 ^4 * 5^4 i.e. 1......to.....810000 which mean b/w these we count all the divisors of 810000.
So using PnC we know we have 5 choices (0 - 4) and 3 places (2, 3 and 5). So all possible divisors will be 5^3 (5 * 5 * 5 all the possible choices) which is 125.

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.