Разбор

Как вычислить $x^{n}$ быстрее чем $O (n)$ ? Например,

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

Можно заметить что $x^{2 n} = (x^{2})^{n}$ , например $x^{100} = (x^{2})^{50}$ .

Для нечетных степеней воспользуемся формулой $x^{2 n + 1} = x \cdot x^{2 n}$ , например $x^{11} = x \cdot x^{10}$ .

Следующая рекуррентная формула дает нам решение за $O (l o g_{2} n)$ :

x^{n} = ⎩ ⎨ ⎧ (x^{2})^{n /2}, n четно x \cdot x^{n - 1}, n нечетно 1, n = 0

При итеративной реализации следует отдельно обработать случай $x = 1$ , $n$ — большое целое число. Например при $x = 1, n = 1 0^{18}$ для вычисления $x^{n}$ следует выполнить $1 0^{18}$ итераций, что даст Time Limit.

Реализация алгоритма

Функция f вычисляет значение $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);
}

Основная часть программы. Читаем входные данные.

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

Вычисляем и выводим ответ $x^{n}$ .

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