Tutorial for Product of Divisors

The problem Product of Divisors asks us to find the last 4 digits of the product of all the divisors of a number. So, suppose we are given a number like 12. The divisors for any number which is not a perfect square will occur in pairs. So, the divisors for the number 12 will be in the following pairs (1,12), (2,6), (3,4). Now, according to the problem statement, we are not to consider the number 12 while computing the answer, so effectively, we can remove the first pair. So, the answer we need will be the product of the numbers 2,6,3,4 which equals 144. Now, the purpose of grouping the numbers in pairs was to show that the product of the numbers in each pair is 12. So, if for a number N, which is not a perfect square, having D divisors, we can always group them into D/2 pairs such that the product of each pair is the original number N. Thus, we effectively transform the answer into N*N*..*N (D-2)/2 times. Thus, The answer in this case becomes N ^ (D/2) where ^ represents the power function and D represents the number of divisors. Thus, for the number 12, the number of divisors is 6, so the answer is 12 ^ ((6-2)/2) = 12 ^ 2 = 144.

Now, let us take the case of a number which is a perfect square. Consider the number 36 which is a perfect square. The divisors of 36 are 1,36,2,18,3,12,4,9,6. So now, if we start grouping them into pairs such that the product of each pair is 36, we get the following pairs (1,36), (2,18), (3,12), (4,9), (6,6). Now, we see that the divisor 6 needs to be repeated to form the pairs of the sort mentioned previously. We have 9 divisors for the number 36. As earlier, we remove 2 of the divisors, that is, the pair (1,36) as the problem statement asks us not to consider the number N while taking the product. Thus we start grouping the numbers into pairs again : (2,18), (3,12), (4,9) and we get one divisor 6 which is left without a divisor to pair up with. So, consider that we group up 6 with 6 itself to get another pair which gives us the value 36. So, the total product will be (36 ^ (number of pairs))/6. So, effectively if we have to calculate the product of divisors for a number N which is a perfect square, our equation becomes N^((D-2)/2) which is N^(D-2)/2. In the earlier case, as D would always be even, D-2 would be even and (D-2)/2 would be an integer. But in this case, as N is a perfect square, (D-2) is odd. We can reframe this as (N^(1/2))^(D-2). Now, as N is a perfect square, N^(1/2) will be an integer. So the answer in this case becomes sqrt(N)^(D-2).

So, we can see that given a number, we can find the required answer using the expressions mentioned above. So now, the only thing left to do is to find the number of divisors. Now, let us see how to calculate the number of divisors of a particular number. Suppose the number N is factorized into its prime factors and their powers as p1^a1 * p2^a2 * ... * pn^an. Then, the number of divisors of the number N including 1 and N are (a1+1)*(a2+1)*...*(an+1). Let us see why this is so. Take the case that N is a prime number, then the prime factorization of N can be p1^1 where p1=N. N has 2 divisors 1 and N so the answer is (1+1) which is 2. Now consider a number N which has prime factorization p1^a1 * p2^a2 * ... * pn^an. Now, suppose a number B which equals N*P where P is a prime number. Now, the prime factorization of B becomes p1^a1 * p2^a2 * ... * pn^an * p^1. Suppose the number N had X divisors. B equals N*P, so all divisors of N are divisors of B. Also, if T is a divisor of B, then so is P*T. Thus, we see that the number of divisors in this case has doubled. That is because of the introduction of P^1 in the sequence, the number of divisors has become X * (1+1). This can easily be extended to introduction of P^Z in the sequence to show that because of this introduction, the number of divisors is increased by a factor (Z+1).

So, now we know how to calculate the number of divisors of a number. We also know that once we know the number of divisors of a number, we can find the required answer using the formulae we derived. But, there is a small catch here. The number N can be pretty large and we need to find the power of N raised to a number which can be a about 100. Also, we need to do this for about 300000 numbers. If we calculate the power of the number modulo some value using an iterative function that iterates over the value of the exponent, our code won't run within time. We can use a nice little trick here to calculate the value of (a^b)%p by using the observation that if 'b' is even, then a^b = a^(b/2) * a^(b/2) and if 'b' is odd, a^b = a*pow(a,b-1). Using this, we can calculate the power of a number pretty quickly taking about log(exponent) iterations.

Thus, the rough outline of the required code would be something as follows :

[code]

Start
Precompute all primes below 500000
Precompute what numbers below 500000 are perfect squares and their squareroots
Take in number of test cases
While there exists a test case we have not processed
Take in the number.
Find the number of divisors.
Calculate the answer using the formulae we derived.
Take the remainder with 10000 while calculating the answers.
Take care to make sure that we print the last 4 digits correctly with necessary number of 0s. Simply taking modulo 10000 will not work.
Print the answer
Stop

[/code]

We leave it to the reader to handle the part where the last 4 digits have to be correctly displayed.