Redaksiya

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

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}$ , for example $x^{100} = (x^{2})^{50}$ .

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

The following recursive formula gives us an $O (l o g_{2} n)$ 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

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

Algorithm realization

The function f computes the value of $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}$ .

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