Разбор

Для возведения в степень $x^{n} m o d 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 нечётно e, 1, n = 0

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

Функция powmod вычисляет значение $x^{n} m o d 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$ .

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} m o d 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))