Піднесення до степеня#4439

Піднесення до степеня (Розбір)

Як обчислити $x^{n}$ x^n швидше ніж $O (n)$ ? Наприклад,

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

Можна помітити що $x^{2 n} = (x^{2})^{n}$ x^{2n} = (x^2)^n, наприклад $x^{100} = (x^{2})^{50}$ x^{100} = (x^2)^{50}.

Для непарних степенів скористаємося формулою $x^{2 n + 1} = x \cdot x^{2 n}$ x^{2n+1} = x \cdot x^{2n}, наприклад $x^{11} = x \cdot x^{10}$ x^{11} = x \cdot x^{10}.

Наступна рекурентна формула дає нам розв'язок за $O (l o g_{2} n)$ O(log_2n):

x^{n} = ⎩ ⎨ ⎧ (x^{2})^{n /2}, n парне x \cdot x^{n - 1}, n непарне 1, n = 0

x^n = \begin{cases} (x^2)^{n/2}, n~парне \\ x \cdot x^{n - 1}, n~непарне \\ 1, n = 0 \end{cases}

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

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

Функція f обчислює значення $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);
}

Основна частина програми. Читаємо вхідні дані.

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

Обчислюємо та виводимо відповідь $x^{n}$ x^n.

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