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

Аналіз алгоритму

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

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

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

Функція powmod обчислює значення $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} 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 реалізація – 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();
    }
}

Python реалізація – pow

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

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

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

print(pow(x, n, m))

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

Функція myPow обчислює значення $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))