[a4] The Rise and Fall of Power.

help
, , ,
1

In this problem a4
i’ve to handle the value of n^n (1 ≤ n ≤ 10^9)

I used long long int for that but it’s not good enough to handle such big number.

Any idea/suggestion how to handle that?

2

look at the constraints…

Each test case consists of one line containing two numbers n and k (1 ≤ n ≤ 109, 1 ≤ k ≤ 9).

maximum value of k is 9… so you need only 18 digits at max… => you can think on getting those 18 digits without really thinking about solving the complete n^n expression

on the other hand if u really want to deal with big big numbers… use arrays as in

int num[NUM_DIGITS]

and store a (0-9) in each of the int array… but you would need to write your own muliply,add, sub,division if you need them

1 Like
3

You don’t need to calculate all that. At max you need to calculate pow(10,k). You only need to calculate first and last k digits. Use some logarithm. If doubt go through solution of any user. Solutions are public on codechef. Use repeated squaring for calculating last k digits as follows :

long long int multiply(int n)
{
  long long int product;
  long long int mod = pow(10,k);
  while(n)
  {
    if(n%2==1) product = (n*product)%mod;
    product = (product * product)%mod;
    n/=2;
  }
  return product;
}

```
3 Likes