5198. Modular Exponentiation

 

Find the value of the expression xn mod m.

 

Input. Three positive integers x, n, m (1 ≤ x, n ≤ 109, 2 ≤ m ≤ 109).

 

Output. Print the value of xn mod m.

 

Sample input

Sample output

2 3 100

8

 

 

SOLUTION

recursion

 

Algorithm analysis

To find the value of xn mod m use the formula:

xn mod m =

 

Let’s consider the iterative exponentiation algorithm.

 

Any integer n can be represented in binary form:

n = bk 2k + … + b1 21 + b0 20

For example:

13 = 11012 = 8 + 4 + 1

Using this representation, the power x13 can be rewritten as a product of powers of two:

x13 = x8 ∙ x4 ∙ x1

To compute the power, it is necessary to multiply only those powers for which the corresponding bit in the binary representation is 1.

To construct any power xn, it is sufficient to have only powers of the form:

x1, x2, x4, x8, x16, …

The algorithm for computing xn scans the bits of the number n from the least significant to the most significant, and at each iteration:

·        If the current bit of the number n is 1, multiply the result res by the current power x;

·        Square the base x;

·        Shift the exponent n one bit to the right (divide n by 2).

 

13 = 11012

 

n

bit

degree x

res

13

1

x1

x1

6

0

x2

x1

3

1

x4

x5

1

1

x8

x13

 

Algorithm implementation – recursion

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

}

 

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

 

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

 

Compute the value of xn mod m.

 

res = powmod(x, n, m);

 

Print the answer.

 

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

 

Algorithm implementation – iteration

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

}

 

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

 

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

 

Compute the value of xn mod m.

 

res = powmod(x, n, m);

 

Print the answer.

 

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

 

Java implementation

 

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 implementation – 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 implementation – pow

Read the input data.

 

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

 

Compute and print the answer.

 

print(pow(x, n, m))

 

Python implementation – recursion

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

 

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