Exponentiation#4439

Exponentiation (Editorial)

How to compute $x^{n}$ x^n faster than $O (n)$ ? For example,

x^{10} = (x^{5})^{2} = (x \cdot x^{4})^{2} = (x \cdot (x^{2})^{2})^{2}

x^{10} = (x^5)^2 = (x \cdot x^4)^2 = (x \cdot (x^2)^2)^2

It can be noted that $x^{2 n} = (x^{2})^{n}$ x^{2n} = (x^2)^n, for example $x^{100} = (x^{2})^{50}$ x^{100} = (x^2)^{50}.

For odd powers, we use the formula $x^{2 n + 1} = x \cdot x^{2 n}$ x^{2n+1} = x \cdot x^{2n}, for example $x^{11} = x \cdot x^{10}$ x^{11} = x \cdot x^{10}.

The following recursive formula gives us an $O (l o g_{2} n)$ O(log_2n) solution:

x^{n} = ⎩ ⎨ ⎧ (x^{2})^{n /2}, n i s e v e n x \cdot x^{n - 1}, n i s o dd 1, n = 0

x^n = \begin{cases} (x^2)^{n/2}, n~is~even \\ x \cdot x^{n - 1}, n~is~odd \\ 1, n = 0 \end{cases}

In an iterative implementation, the case when $x = 1$ x = 1 and $n$ is a large integer should be handled separately. For example, when $x = 1$ x = 1 and $n = 1 0^{18}$ n = 10^{18}, computing $x^{n}$ x^n would require $1 0^{18}$ 10^{18} iterations, which would result in a Time Limit.

Algorithm realization

The function f computes the value of $x^{n}$ x^n.

long long f(long long x, long long n)
{
  if (n == 0) return 1;
  if (n % 2 == 0) return f(x * x, n / 2);
  return x * f(x, n - 1);
}

The main part of the program. Read the input data.

scanf("%lld %lld",&x,&n);

Compute and print the answer $x^{n}$ x^n.

res = f(x,n);
printf("%lld\n",res);