Quvvətə yüksəltmə#4439

Quvvətə yüksəltmə (Həll təhlili)

$x^{n}$ x^n ifadəsini $O (n)$ -dən daha sürətli necə hesablamaq olar? Məsələ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

Görə bilərik ki, $x^{2 n} = (x^{2})^{n}$ x^{2n} = (x^2)^n, məsələn $x^{100} = (x^{2})^{50}$ x^{100} = (x^2)^{50}.

Tək qüvvətlər üçün $x^{2 n + 1} = x \cdot x^{2 n}$ x^{2n+1} = x \cdot x^{2n} düsturundan istifadə edəcəyik, məsələn $x^{11} = x \cdot x^{10}$ x^{11} = x \cdot x^{10}.

Aşağıdakı rekurret düstur bizə $O (l o g_{2} n)$ O(log_2n) həllini verir:

x^{n} = ⎩ ⎨ ⎧ (x^{2})^{n /2}, n c u ¨ t x \cdot x^{n - 1}, n t ə k 1, n = 0

x^n = \begin{cases} (x^2)^{n/2}, n~cüt \\ x \cdot x^{n - 1}, n~tək \\ 1, n = 0 \end{cases}

İterativ tətbiqdə $x = 1$ x = 1, $n$ — böyük tam ədəd halları ayrıca işlənməlidir. Məsələn, $x = 1, n = 1 0^{18}$ x = 1, n = 10^{18} olduqda, $x^{n}$ x^n hesablamaq üçün $1 0^{18}$ 10^{18} iterasiya yerinə yetirilməlidir ki, bu da Time Limit yaradacaq.

Alqoritmin tətbiqi

f funksiyası $x^{n}$ x^n qiymətini hesablamaqdadır.

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);
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

$x^{n}$ x^n cavabını hesablayır və çap edirik.

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