Qüvvətə yüksəltmə (#5198)

Alqoritm Analizi

$x^{n} mod m$ -i hesablamaq üçün aşağıdakı formuldan istifadə edəcəyik:

x^{n} mod m = ⎩ ⎨ ⎧ (x^{n /2} mod m)^{2} mod m, ə g ə r n c \overset{u}{¨} t r ə q ə m d i r, (x \cdot x^{n - 1}) mod m mod m, ə g ə r n t ə k d i r, 1, n = 0

x^{n} mod m = (x^{n /2} mod m)^{2} mod m,

əgər $n$ cüt rəqəmdir, və $x \cdot (x^{n - 1} mod m) mod m$ , əgər $n$ təkdir.

Alqoritm İmplementasiyası

powmod funksiyası $x^{n} mod m$ dəyərini hesablayır.

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;
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxumaq.

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

$x^{n} mod m$ dəyərini hesablamaq.

res = powmod(x, n, m);

Cavabı çap etmək.

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

Java İmplementasiyası

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 İmplementasiyası – 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 İmplementasiyası – pow

Giriş məlumatlarını oxumaq.

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

Cavabı hesabla və çap et.

print(pow(x, n, m))

Python İmplementasiyası – rekurziya

myPow funksiyası $x^{n} mod m$ dəyərini hesablayır.

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

Proqramın əsas hissəsi. Giriş məlumatlarını oxumaq.

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

Cavabı hesabla və çap et.

print(myPow(x, n, m))