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

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

Піднесення до степеня — це математична операція, що позначається як $x^{n}$ x^n, яка включає два числа: основу $x$ та показник степеня $n$ . Якщо $n$ — натуральне число, то операція піднесення до степеня зводиться до послідовного множення основи саму на себе: $x^{n}$ x^n — це добуток $n$ множників, кожен з яких дорівнює $x$ : $x^{n} = x \cdot x \cdot ... \cdot x$ x^n = x \cdot x \cdot ... \cdot x.

Як обчислити $x^{n}$ x^n за заданими $x$ та $n$ ? Можна скористатися одним циклом зі складністю $O (n)$ . Лінійний алгоритм пройде за часом, оскільки $n \leq 1 0^{7}$ n \le 10^7.

Можна також скористатися швидким піднесенням до степеня:

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

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

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

Скористаємося $64$ бітним цілочисельним типом long long. Читаємо вхідні дані.

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

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

res = 1;
for (i = 1; i <= n; i++)
  res = (res * x) % 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)
{
  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);

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

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

Java реалізація — лінійна складність

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

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

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

Обчислюємо та виводимо відповідь. Використовуємо вбудовану функцію pow для обчислення виразу $x^{n} m o d m$ x^n~mod~m.

print(pow(x, n, m))

Python реалізація — цикл

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

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

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

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

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

print(res)