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 =
Algorithm
realization
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);
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 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))