Editorial

To find the value of $x^{n} m o d m$ use the formula:

x^{n} m o d m = ⎩ ⎨ ⎧ (x^{2})^{n /2} m o d m, i f n i s e v e n, (x \cdot x^{n - 1}) m o d m, i f n i s o dd, 1, n = 0

Algorithm realization

The powmod function computes the value of $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;
}

The main part of the program. Read the input data.

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

Compute the value of $x^{n} m o d m$ .

res = powmod(x, n, m);

Print the answer.

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

Java realization

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 realization — 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 realization — pow

Read the input data.

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

Compute and print the answer.

print(pow(x, n, m))

Python realization — recursion

The myPow function computes the value of $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

The main part of the program. Read the input data.

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

Compute and print the answer.

print(myPow(x, n, m))