Qüvvətə yüksəltmə#273

Qüvvətə yüksəltmə (Həll təhlili)

Qüvvətə yüksəltmə — $x^{n}$ x^n kimi işarə olunan riyazi əməliyyatdır və iki ədədi əhatə edir: əsas $x$ və qüvvət göstəricisi $n$ . Əgər $n$ natural ədəddirsə, qüvvətə yüksəltmə əməliyyatı əsasın özü ilə ardıcıl vurulmasına gətirilir: $x^{n}$ x^n — hər biri $x$ -ə bərabər olan $n$ vuruğun hasilidir: $x^{n} = x \cdot x \cdot ... \cdot x$ x^n = x \cdot x \cdot ... \cdot x.

Verilmiş $x$ və $n$ üçün $x^{n}$ x^n necə hesablanır? Mürəkkəbliyi $O (n)$ olan bir dövrdən istifadə etmək olar. Xətti alqoritm vaxt baxımından keçəcək, çünki $n \leq 1 0^{7}$ n \le 10^7.

Eyni zamanda sürətli qüvvətə yüksəltmədən də istifadə etmək olar:

x^{n} m o d m = ⎩ ⎨ ⎧ (x^{2})^{n /2}, ə g ə r n c u ¨ t d u ¨ r s ə, x \cdot x^{n - 1}, ə g ə r n t ə k d i r s ə, 1, n = 0

x^n~mod~m = \begin{cases} (x^2)^{n/2}, əgər~n~cütdürsə,\\ x \cdot x^{n-1}, əgər~n~təkdirsə, \\ 1, n = 0 \end{cases}

Alqoritmin realizasiyası

$64$ bitlik tam ədəd tipi long long-dan istifadə edəcəyik. Giriş məlumatlarını oxuyuruq.

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

$x^{n} m o d m$ x^n~mod~m dəyərini dövr vasitəsilə hesablayırıq.

res = 1;
for (i = 1; i <= n; i++)
  res = (res * x) % m;

Cavabı çıxarırıq.

printf("%lld\n",res);

Sürətli qüvvətə yüksəltmə vasitəsilə realizasiya

PowMod funksiyası $x^{n} m o d m$ x^n~mod~m ifadəsinin dəyərini hesablayır.

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

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

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

Cavabı hesablayır və çıxarırıq.

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

Java realizasiyası — xətti mürəkkəblik

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    long x = con.nextLong(),
         n = con.nextLong(),
         m = con.nextLong();
    long res = 1;
    for (int i = 1; i <= n; i++) res = (res * x) % m;
    System.out.println(res);
    con.close();
  }
}

Java

Java realizasiyası — O(log2n)

import java.util.*;

public class Main
{
  static long PowMod(long x, long n, long m)
  {
    if (n == 0) return 1;
    if (n % 2 == 0) return PowMod((x * x) % m, n / 2, m);
    return (x * PowMod(x, n - 1, m)) % m;
  }
	
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    long x = con.nextLong();
    long n = con.nextLong();
    long m = con.nextLong();
    long res = PowMod(x,n,m);
    System.out.println(res);
    con.close();
  }
}

Java

Java realizasiyası — powMod

import java.util.*;
import java.math.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);	  
    BigInteger x = con.nextBigInteger();
    BigInteger n = con.nextBigInteger();
    BigInteger m = con.nextBigInteger();
    System.out.println(x.modPow(n,m));    
    con.close();
  }
}

Java

Python realizasiyası — pow

Giriş məlumatlarını oxuyuruq.

x, n, m = map(int, input().split())

Cavabı hesablayır və çıxarırıq. $x^{n} m o d m$ x^n~mod~m ifadəsini hesablamaq üçün daxili pow funksiyasından istifadə edirik.

print(pow(x, n, m))

Python realizasiyası — dövr

Giriş məlumatlarını oxuyuruq.

x, n, m = map(int, input().split())

$x^{n} m o d m$ x^n~mod~m dəyərini dövr vasitəsilə hesablayırıq.

res = 1
for i in range(1, n + 1):
  res = (res * x) % m

Cavabı çıxarırıq.

print(res)