Contest Link: http://www.codechef.com/CDSM2014

Problem Link: http://www.codechef.com/problems/PPOW

Author and Editorialist: Prateek Kumar

**PREREQUISITES:**

Pre- Computations, Storage of large numbers in an array.

**PROBLEM:**

You are given two numbers a and b, and you are supposed to calculate the value of a^{b} for a number of test cases.

**EXPLANATION:**

- The constraint on b is 4000 and on a is 9. The value is large, so we have to store the value of a
^{b}in an integer array. This task was accomplished by simple modulo and division of the values. This allows to store the digits of number in an array.

There is a problem http://www.codechef.com/problems/FCTRL2/ in the easy section that deals with the**storage of large numbers in an array**.

The**tutorial**for the same is here: http://www.codechef.com/wiki/tutorial-small-factorials .

**This tutorial covers in detail the storage of large numbers in an array**.

2.There was also the issue of time limit. Instead of computing the value of a^b for each test case, we can calculate the answer for each and every possible values of a and b store it in a 2-D array, before taking any input. **This is known as pre-computation**.

Also, when we calculate a^4, we also get the answer a^1, a^2 , a^3 at the iterations and finally get a^4. We can calculate all these values for a particular (a) by iterating from 1 to 4000 in one go. Calculate these for all values of a and store them in a 2-D array.

- This problem would have been very simple in python, and in JAVA using the BigInteger class. For this reason, python was not in the language choice and the BigInteger solution was not fast enough to pass the specified time limit.

**SIMILAR APPROACH PROBLEMS:**

http://www.codechef.com/problems/FCTRL2/

**AUTHOR’S SOLUTIONS:**

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