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

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

Для піднесення до степеня $x^{n} m o d m$ x^n~mod~m скористаємося формулою:

x^{n} m o d m = ⎩ ⎨ ⎧ (x^{2})^{n /2} m o d m, якщо n парне, (x \cdot x^{n - 1}) m o d m, якщо n непарне, 1, n = 0

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

Розглянемо ітераційний алгоритм піднесення до степеня.

Будь-яке число $n$ можна представити в двійковій системі:

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

Наприклад:

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

13 = 1101_2 = 8 + 4 + 1

Використовуючи це представлення, степінь $x^{13}$ x^{13} можна переписати як добуток степенів двійки:

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

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

Для обчислення степеня необхідно множити тільки ті степені, де біт у двійковому представленні дорівнює $1$ .

Щоб зібрати будь-яку степінь $x^{n}$ x^n, достатньо мати тільки степені виду:

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

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

Алгоритм обчислення $x^{n}$ x^n переглядає біти числа $n$ від молодшого до старшого і на кожній ітерації:

якщо поточний біт числа $n$ дорівнює $1$ , множимо відповідь $r es$ на поточну степінь $x$ ;
основу $x$ підносимо до квадрату;
показник степеня $n$ зсовуємо вправо на один біт (ділимо $n$ на $2$ ).

13 = 110 1_{2}

13 = 1101_2

n	біт	степінь x	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}

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

Функція powmod обчислює значення $x^{n} m o d m$ x^n~mod~m.

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

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

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

Обчислюємо значення $x^{n} m o d m$ x^n~mod~m.

res = powmod(x, n, m);

Виводимо відповідь.

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

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

Функція powmod обчислює значення $x^{n} m o d m$ x^n~mod~m.

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++

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

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

Обчислюємо значення $x^{n} m o d m$ x^n~mod~m.

res = powmod(x, n, m);

Виводимо відповідь.

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

Java реалізація

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 реалізація — 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 реалізація — pow

Читаємо вхідні дані.

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

Обчислюємо і виводимо відповідь.

print(pow(x, n, m))

Python реалізація — рекурсія

Функція myPow обчислює значення $x^{n} m o d m$ x^n~mod~m.

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

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

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

Обчислюємо і виводимо відповідь.

print(myPow(x, n, m))