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

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

$x^{n} m o d m$ x^n~mod~m üçün üstəqaldırma etmək üçün belə bir formuldan istifadə edəcəyik:

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

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

Üstəqaldırma üçün iterativ algoritmə baxaq.

Hər hansı bir $n$ ədədini ikilik sistemdə təmsil etmək olar:

n = b_{k} 2^{k} + ... + b_{1} 2^{1} + b_{0} 2^{0}

n = b_k 2^k + ... + b_1 2^1 + b_0 2^0

Məsələn:

13 = 110 1_{2} = 8 + 4 + 1

13 = 1101_2 = 8 + 4 + 1

Bu təmsil etmədən istifadə edərək, $x^{13}$ x^{13} üstünü ikilik gücünün hasilinə yazmaq olar:

x^{13} = x^{8} \cdot x^{4} \cdot x^{1}

x^{13} = x^8 \cdot x^4 \cdot x^1

Üstün hesablanması üçün yalnız ikəlik təmsildəki bitin $1$ bərabər olduğu üstlər vurulmalıdır.

Hər hansı $x^{n}$ x^n üstünə çatmaq üçün yalnız aşağıdakı üstlərə malik olmaq kifayətdir:

x^{1}, x^{2}, x^{4}, x^{8}, x^{16}, ...

x^1, x^2, x^4, x^8, x^{16}, ...

$x^{n}$ x^n hesablanması üçün algoritm $n$ ədədinin bitlərini sağdan sola doğru baxır və hər iterasiyada:

əgər $n$ ədədinin cari biti $1$ bərabərsə, cavabı ( $r es$ ) cari $x$ üstə vururuq;
əsas $x$ kvadrata yüksəlir;
üst $n$ sağa doğru bir bit sürüşdürülür ( $n$ 2-yə bölünür).

13 = 110 1_{2}

13 = 1101_2

n	bit	x üstü	res
13	1	$x^{1}$ x^1	$x^{1}$ x^1
6	0	$x^{2}$ x^2	$x^{1}$ x^1
3	1	$x^{4}$ x^4	$x^{5}$ x^5
1	1	$x^{8}$ x^8	$x^{13}$ x^{13}

Algoritmin təsviri - rekursiya

powmod funksiyası $x^{n} m o d m$ x^n~mod~m 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. Daxil olan məlumatları oxuyuruq.

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

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

res = powmod(x, n, m);

Cavabı çıxarırıq.

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

Algoritmin təsviri – iterasiya

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

long long powmod(long long x, long long n, long long m)
{
  long long res = 1;
  while (n > 0)
  {
    if (n & 1) res = (res * x) % m;
    x = (x * x) % m;
    n >>= 1;
  }
  return res;
}

C++

Proqramın əsas hissəsi. Daxil olan məlumatları oxuyuruq.

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

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

res = powmod(x, n, m);

Cavabı çıxarırıq.

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

Java təsviri

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 təsviri — BigInteger

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

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

Java

Python təsviri — pow

Daxil olan məlumatları oxumaq.

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

Hesablamaq və çıxarmaq.

print(pow(x, n, m))

Python təsviri — rekursiya

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

def myPow(x, n, m):
  if (n == 0): return 1
  if (n % 2 == 0): return myPow((x * x) % m, n / 2, m)
  return (x * myPow(x, n - 1, m)) % m

Proqramın əsas hissəsi. Daxil olan məlumatları oxuyuruq.

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

Hesablamaq və çıxarmaq.

print(myPow(x, n, m))